Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

Language:
M × N Puzzle
 Time Limit: 4000MS Memory Limit: 131072K Total Submissions: 4143 Accepted: 1145

Description

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

 1 6 2 4 0 3 7 5 9 10 8 11

DOWN

 1 0 2 4 6 3 7 5 9 10 8 11
LEFT
 1 2 0 4 6 3 7 5 9 10 8 11

UP

 1 2 3 4 6 0 7 5 9 10 8 11

RIGHT

 1 2 3 4 0 6 7 5 9 10 8 11

UP

 1 2 3 4 5 6 7 0 9 10 8 11
UP
 1 2 3 4 5 6 7 8 9 10 0 11

LEFT

 1 2 3 4 5 6 7 8 9 10 11 0

GOAL

Given an M × N puzzle, you are to determine whether it can be solved.

Input

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

Output one line for each test case containing a single word YES if the puzzle can be solved and NO otherwise.

Sample Input

```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```

Sample Output

```YES
NO```

Source

[Submit]   [Go Back]   [Status]   [Discuss]