Lilypad Pond (lily.X)
Farmer Ran 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 practicing her ballet moves by jumping from one lilypad
to another and is currently located at one of the lilypads. She
wants to travel to another lilypad in the pond by jumping from one
lilypad to another.
Surprising only to the uninitiated, Bessie's jumps between lilypads
always appear as a chess-knight's move: one move in one direction
and then two more in the orthogonal direction (or perhaps two in
one direction and then one in the orthogonal direction).
Farmer Ran is observing Bessie's ballet drill and realizes that
sometimes she can not jump to her destination lilypad because
intermediary lilypads are missing.
Ever thrifty, Farmer Ran wants to place a minimum of additional lilypads,
at knight's-moves away, so she can complete her quest. Of course, lilypads
cannot be placed where rocks are present.
Help Farmer Ran determine the minimum number of additional lilypads
he has to place. Also determine the minimum number of jumps required
to reach the destination when placing that minimum number of
additional lilypads in some optimal location. Finally, determine
the total number of unique ways Bessie can jump from the start to
the end in the minimum number of jumps (after the smallest number
of lily pads is placed in locations as needed, of course!) The final
number includes jumps using any of the possible ways the new lilypads
are placed... .
PROBLEM NAME: lily.X
INPUT FORMAT:
* Line 1: Two space-separated integers: M and N
* 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 in place; 2 indicates rock in
place; 3 indicates the lilypad Bessie starts on; 4 indicates
the lilypad Bessie wants to travel to.
SAMPLE INPUT:
4 8
0 0 0 1 0 0 0 0
0 0 0 0 0 2 0 1
0 0 0 0 0 4 0 0
3 0 0 0 0 0 1 0
INPUT DETAILS:
The ponds has 4 rows and 8 columns. Bessie is at row 4 column 1, and she
wants to reach row 3 column 6. A rock and five lilypads are present.
OUTPUT FORMAT:
* Line 1: One integer: the minimum number of additional lilypads
required. If it is not possible to help Bessie jump to her
destination, print -1.
* Line 2: One integer: the minimum number of jumps Bessie must make
when placing the minimum number of additional lilypads. Do not
output this line if line 1 contains -1.
* Line 3: One integer: the number of paths from start to end that uses
the minimum number of additional pads and the minimum number
of jumps calculated in line 2. Do not output this line if line
1 contains -1.
SAMPLE OUTPUT:
2
6
2
OUTPUT DETAILS:
Two lilypads are required as shown by the x's in each of the two
instances below:
0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0
0 x 0 0 0 2 0 1 0 0 0 0 0 2 0 1
0 0 0 0 x 4 0 0 0 0 x 0 x 4 0 0
3 0 0 0 0 0 1 0 3 0 0 0 0 0 1 0
Bessie must make at least 6 jumps to reach destination and there
are two different paths of 6 jumps as shown below.
0 0 0 C 0 0 0 0 0 0 0 C 0 0 0 0
0 B 0 0 0 2 0 F 0 0 0 0 0 2 0 F
0 0 0 0 D G 0 0 0 0 B 0 D G 0 0
A 0 0 0 0 0 E 0 A 0 0 0 0 0 E 0