6229번 - Bronze Lilypad Pond 다국어

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; M1 != M2) 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.

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