P1606 [USACO07FEB] Lilypad Pond G

FJ has installed a beautiful pond for his cows' aesthetic 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 John is observing Bessie's ballet drill and realizes that sometimes she might not be able to jump to her destination lilypad because intermediary lilypads are missing. Ever thrifty, he wants to place additional lilypads so she can complete her quest (perhaps quickly, perhaps by using a large number of intermediate lilypads). Of course, lilypads cannot be placed where rocks already intrude on a cell. Help Farmer John determine the minimum number of additional lilypads he has to place, and in how many ways he can place that minimum number.

无

无

### 样例解释 池塘分成四行五列，贝西的起点在第二行第一列，想去的终点在第四行第四列，池塘里一共有三朵莲花和一块石头。 最少需要两朵莲花，有三种方式可以放置， 如下 $\verb!X!$ 所示： $$\begin{bmatrix} \verb!10000! \\ \verb!30X00! \\ \verb!00200! \\ \verb!0X040! \\ \end{bmatrix},\begin{bmatrix} \verb!10X00! \\ \verb!30000! \\ \verb!0X200! \\ \verb!00040! \\ \end{bmatrix},\begin{bmatrix} \verb!10X00! \\ \verb!3000X! \\ \verb!00200! \\ \verb!00040! \\ \end{bmatrix} $$