P2411 [USACO07FEB] Silver Lilypad Pond S

To entertain and exercise the cows, Farmer John built a beautiful pond. This rectangular pond is divided into $M \times N$ cells ($1 \le M, N \le 30$). Some cells are surprisingly sturdy lilypads, some cells are rocks, and the rest are just beautiful, pure, azure water. Bessie is practicing ballet. She is standing on a lilypad and wants to jump to another lilypad. She can only jump from one lilypad to another; she cannot land in water or on rocks. Bessie’s steps are like a knight’s moves in chess: each time she either moves one square horizontally and then two squares vertically, or two squares vertically and then one square horizontally. At most, Bessie has eight possible directions to move. John has been watching Bessie’s ballet practice and noticed that sometimes she cannot reach the destination because some lilypads are missing along the way. So he wants to add a few lilypads to help Bessie complete the task. Being thrifty as always, John wants to add the minimum number of lilypads; of course, lilypads cannot be placed on rocks. Please help John determine the minimum number of lilypads that must be added. Under the condition of adding the fewest lilypads, determine the minimum number of jumps Bessie needs to go from the start to the target. Finally, under the same minimum additions, determine the number of paths whose length equals that minimum number of jumps.

The first line contains two integers separated by a space: $M$ and $N$. Lines $2$ through $M + 1$: the $(i + 1)$-th line contains $N$ integers separated by spaces, describing the $i$-th row of the pond: `0` for water, `1` for a lilypad, `2` for a rock, `3` for Bessie’s starting cell, and `4` for Bessie’s target cell.

The first line contains a single integer: the minimum number of lilypads that must be added; if there is no solution, output $-1$. The second line contains a single integer: under the condition of adding the fewest lilypads, the minimum number of jumps Bessie needs from the start to the target; if the first line is $-1$, do not output this line. The third line contains a single integer: under the condition of adding the fewest lilypads, the number of paths whose length equals the number in the second line; if the first line is $-1$, do not output this line.

The pond has four rows and eight columns. Bessie’s start is at row 4, column 1, and her target is at row 3, column 6. There are five lilypads and one rock in the pond. At least two lilypads need to be added, at the positions marked with `x`: ``` 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 needs at least six jumps. Two different sequences of jumps are as follows: ``` 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 ``` Translated by ChatGPT 5