2013
11-12

# M × N Puzzle

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.

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

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;

public class Main {
static final int M = 1000+2;
static final int N = 1000000+10;
static int sort[] = new int[N],map[][] = new int[M][M];
public static void main(String []args) throws Exception{

int i,j,n,m,top,a,b;
int num[] = new int[N];

while(true){
n = Get_Num(cin);
m = Get_Num(cin);
if(n==0 && m==0) break;
for(i=top=0;i< n;++i)
for(j=0;j< m;++j){
map[i][j] = Get_Num(cin);
}
if(m%2==1){
for(i=0;i< n;++i)
for(j=0;j< m;++j) if(map[i][j]>0)
num[top++] = map[i][j];
}else{
for(i=0;i< m;++i)
for(j=0;j< n;++j) if(map[j][i]>0)
num[top++] = map[j][i];
}
a = merge(num,0,top-1);
if(m%2==1){
if(a%2==0) System.out.println("YES");
else System.out.println("NO");
}
else{
for(i=top=0;i< n;++i)
for(j=0;j< m;++j)
map[i][j] = ++top;
map[n-1][m-1] = 0;
for(i=top=0;i< m;++i)
for(j=0;j< n;++j) if(map[j][i]>0)
num[top++] = map[j][i];
b = merge(num,0,top-1);
if(a%2==b%2) System.out.println("YES");
else System.out.println("NO");
}
}

}

public static int Get_Num(StreamTokenizer cin)throws Exception{
cin.nextToken();
return (int)cin.nval;
}

public static int merge(int num[],int left,int right){

if(left==right){
sort[left] = num[left];
return 0;
}
int mid,i,j,ans=0,top=0;
mid = (left+right)/2;
ans = merge(num,left,mid)%2;
ans += merge(num,mid+1,right)%2;

i = left ; j = mid+1;
while(i<=mid && j<=right){
if(num[i]>num[j]){
ans += (mid-i+1)%2;
sort[top++] = num[j++];
}
else{
sort[top++] = num[i++];
}
}
while(i<=mid)
sort[top++] = num[i++];
while(j<=right)
sort[top++] = num[j++];
for(i=left;i<=right;++i)
num[i] = sort[i-left];

return ans;
}
}

1. 如果两个序列的最后字符不匹配（即X [M-1]！= Y [N-1]）
L（X [0 .. M-1]，Y [0 .. N-1]）= MAX（L（X [0 .. M-2]，Y [0 .. N-1]），L（X [0 .. M-1]，Y [0 .. N-1]）
这里写错了吧。

2. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。

3. int half(int *array,int len,int key)
{
int l=0,r=len;
while(l<r)
{
int m=(l+r)>>1;
if(key>array )l=m+1;
else if(key<array )r=m;
else return m;
}
return -1;
}
这种就能避免一些Bug
l,m,r
左边是l,m;右边就是m+1,r;