#P2971. "Switchback"

    ID: 1981 远端评测题 3000ms 64MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>Northeastern Europe 2004, Western Subregion

"Switchback"

Description

A construction firm, which you work for, has signed a contract to complete construction of attraction called “Switchback”. The building site is a rectangle which is split into NxM squares (1 ≤ N, M ≤ 50), N rows down, M columns across. The square in the north-west corner of the building site is (1, 1), while the square in the south-east corner is (N, M).

By the moment of signing the contract the following work has already been done at the attraction building site. First, a mast was built in each of the squares. The height of the mast in the square (i, j) is Hij (1 ≤ Hij ≤ 100, natural). Second,  construction of a launching complex was started at the top of the mast with coordinates (a, b), where 1 ≤ aN, 1 ≤ bM.

The idea of the attraction is the following. A small carriage with passengers moves from one square to another adjacent square, square by square. It starts moving from the square with the launching complex and moves until it stops. It moves on rails built on tops of masts according to the following rules:

  • at the launching complex the carriage is slightly pushed so to start moving in any direction downwards;
  • on arrival to the next square the carriage can continue its movement in the same direction or can turn 90° to the right or to the left;
  • the carriage’s speed increases by one for each unit of height reduction while moving downwards; the carriage can not move downwards if its current speed is zero;
  • the carriage’s speed decreases by two for each unit of height increment while moving upwards. If the carriage moves upwards than its initial speed has to be sufficient to reach the next square;
  • the carriage’s speed during a transition to an adjacent square decreases by one while moving horizontally;
  • safety rules forbid to change the carriage’s speed during transition to an adjacent square by more than 2 units;
  • the carriage has brakes which can be used only to stop the carriage on arrival to the final square. However, safety rules forbid using brakes if the carriage’s speed on arrival to this square is more than three units.

The number of squares visited by the carriage during its trip is called attraction length. If the carriage visits a square more than once than each of the visits counts. The first square of the path does not count.

The construction firm has to build rails on tops of the masts. As the only programmer in the firm, you need to write a program which can find the longest possible path according to the rules above. It is guaranteed that this path exists and its length is greater than zero.

Input

The first line of the input contains values N, M, a, b. The next N lines contain values Hi,j, M values per line. The numbers in the input file’s lines are separated by one or more spaces.

Output

The output contains several lines. The first line contains an attraction length k. Next k lines contain coordinates of squares and describe the longest path.

5 5 1 1
10 8 6 3 4
9  7 6 5 8
4  5 5 2 1
2  3 5 7 8
1  4 3 3 2
14
2 1
2 2
1 2
1 3
2 3
3 3
3 2
3 1
4 1
4 2
5 2
5 3
5 4
5 5

Source

Northeastern Europe 2004, Western Subregion