Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
M × N Puzzle
Time Limit: 4000MSMemory Limit: 131072K
Total Submissions: 4157Accepted: 1146

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:

162
403
759
10811

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:

123
456
789
10110

The following steps solve the puzzle given above.

START

162
403
759
10811

DOWN

102
463
759
10811
LEFT
120
463
759
10811

UP

123
460
759
10811

RIGHT

123
406
759
10811

UP

123
456
709
10811
UP
123
456
789
10011

LEFT

123
456
789
10110

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]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator