当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。
The Eight Puzzle, among other sliding-tile puzzles, is one of the famous problems in artificial intelligence. Along with chess, tic-tac-toe and backgammon, it has been used to study search algorithms.
The Eight Puzzle can be generalized into an M × N Puzzle where at least one of M and N is odd. The puzzle is constructed with MN − 1 sliding tiles with each a number from 1 to MN − 1 on it packed into a M by N frame with one tile missing. For example, with M = 4 and N = 3, a puzzle may look like:
| 1 | 6 | 2 |
| 4 | 0 | 3 |
| 7 | 5 | 9 |
| 10 | 8 | 11 |
Let's call missing tile 0. The only legal operation is to exchange 0 and the tile with which it shares an edge. The goal of the puzzle is to find a sequence of legal operations that makes it look like:
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
| 10 | 11 | 0 |
The following steps solve the puzzle given above.
START |
| DOWN |
| LEFT ⇒ |
| UP |
| … | ||||||||||||||||||||||||||||||||||||||||||||||||
RIGHT |
| UP |
| UP ⇒ |
| LEFT |
| GOAL | ||||||||||||||||||||||||||||||||||||||||||||||||
Given an M × N puzzle, you are to determine whether it can be solved.
The input consists of multiple test cases. Each test case starts with a line containing M and N (2 ≤ M, N ≤ 999). This line is followed by M lines containing N numbers each describing an M × N puzzle.
The input ends with a pair of zeroes which should not be processed.
Output one line for each test case containing a single word YES if the puzzle can be solved and NO otherwise.
3 3 1 0 3 4 2 5 7 8 6 4 3 1 2 5 4 6 9 11 8 10 3 7 0 0 0
YES NO
| 时间上限 | 内存上限 |
| 4000 | 131072 |