Tianjin University Online Judge
Contests Virtual Contests Problems Submit Runs Status Rank List Forum

2760.   Bronze Lilypad Pond
Time Limit: 1.0 Seconds   Memory Limit: 65536K
Total Runs: 552   Accepted Runs: 223    Multiple test files

Farmer John has installed a beautiful pond for his cows' esthetic enjoyment and exercise. The rectangular pond has been partitioned into square cells of M rows and N columns (1 ≤ M ≤ 30; 1 ≤ N ≤ 30). Some of the cells have astonishingly sturdy lilypads; others have rocks; the remainder are just beautiful, cool, blue water.

Bessie is practising her ballet moves by jumping from one lilypad to another and is currently located at one of the lilypads (see the input data for the location's specifier). She wants to travel to another lilypad in the pond by jumping from one lilypad to another. She can jump neither into the water nor onto a rock.

Surprising only to the uninitiated, Bessie's jumps between lilypads always appear as a sort of chess-knight's move: move M1 (1 ≤ M1 ≤ 30) 'squares' in one direction and then M2 (1 ≤ M2 ≤ 30; M1M2) more in an orthogonal direction (or perhaps M2 in one direction and then M1 in an orthogonal direction). Bessie sometimes might have as many as eight choices for her jump.

Given the pond layout and the format of Bessie's jumps, determine the smallest number of leaps that Bessie must make to move from her starting location to her final destination, a feat which is always possible for the given test data.


* Line 1: Four space-separated integers: M, N, M1, and M2

* Lines 2..M + 1: Line i + 1 describes row i of the pond using N space-separated integers with these values: 0 indicates empty water; 1 indicates a lilypad; 2 indicates a rock; 3 indicates the lilypad Bessie upon which she starts; 4 indicates the lilypad that is Bessie's destination.


* Line 1: A single integer that is the minimum number of jumps between lilypads that Bessie must make to travel from her starting place to her destination.

Sample Input

4 5 1 2
1 0 1 0 1
3 0 2 0 4
0 1 2 0 0
0 0 0 1 0

Sample Output


Input Details

Bessie starts on the left in row 2; her destination is on the right in row 2. Several lilypads and rocks occupy the pond.

Output Details

Bessie cleverly hops onto the pad at row 1, column 3 on her way to the right hand side.

Source: USACO 2007 February Competition
Submit   List    Runs   Forum   Statistics

Tianjin University Online Judge v1.3.0
Maintance:Fxz. Developer: SuperHacker, G.D.Retop, Fxz