当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。
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.
4 5 1 0 0 0 0 3 0 0 0 0 0 0 2 0 0 0 0 0 4 0
2 3
Two lilypads are required. There are three ways to place them: row 4 column 2 and row 2 column 3; row 1 column 3 and row 3 column 2; or row 1 column 3 and row 2 column 5:
R1C2,R2C3 R1C3,R3C2 R1C3,R2C5
1 0 0 0 0 1 0 X 0 0 1 0 X 0 0
3 0 X 0 0 3 0 0 0 0 3 0 0 0 X
0 0 2 0 0 0 X 2 0 0 0 0 2 0 0
0 X 0 4 0 0 0 0 4 0 0 0 0 4 0
| 时间上限 | 内存上限 |
| 2000 | 65536 |