| Time Limit: 4000MS | Memory Limit: 131072K | |
| Total Submissions: 4112 | Accepted: 1140 |
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 |
|
DOWN |
|
LEFT ⇒ |
|
UP |
|
… |
||||||||||||||||||||||||||||||||||||||||||||||||
|
RIGHT |
|
UP |
|
UP ⇒ |
|
LEFT |
|
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
题意：8数码问题的升级，就是通过移动空格（用0代替）使得原来状态变成有序的1234......0，不过，这题是N*M数码。
题解：N*M都挺大的，搜索必然不行。考虑终态，实际就是逆序数为0的状态，然后四种操作方式分为：左右移动，对原序列的逆序数不影响；上下移动，如下：
-------------0***********
***********x-------------
x是任意数，现在要把x移上去，那么***********中，假设有a个大于x，b个小于x，那么移动之后逆序数就会加上一个b-a，x所能影响的也就是这些罢了，除此之外，其他都不变。
接着，如果列数为偶数，那么******的个数就是奇数，b,a奇偶性互异，b-a为奇数，所以移动一次后，原序列的逆序数的奇偶性变了。
考虑到最后0会移动到最后一行，所以奇偶性会改变n-i次(i为0的行数)，只需判断最后是否是偶数即可。
反之，如果列数为奇数，那么******的个数就是偶数，b,a奇偶性相同，b-a为偶数，所以移动一次后，原序列的逆序数的奇偶性没变。
因为无论怎么移，奇偶性都不变，所以说一开始初态的奇偶性就必须与末态一致。
题意来自http://blog.****.net/tmeteorj/article/details/8530105
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define inf 2e9
#define met(a,b) memset(a,b,sizeof a)
typedef long long ll;
using namespace std;
const int N = *+;
const int M = 4e5+;
int n,m,tot=,cnt=;
int head[N],ans[N];
int tree[N];
int a[N];
void add(int k,int num) {
while(k<=*-) {
tree[k]+=num;
k+=k&(-k);
}
}
int Sum(int k) {
int sum=;
while(k>) {
sum+=tree[k];
k-=k&(-k);
}
return sum;
}
int main() { while(scanf("%d%d",&n,&m),n||m) {
int x,y,t,s=,nu=;
for(int i=; i<=n; i++)
for(int j=; j<=m; j++) {
scanf("%d",&t);
if(t==)
x=i,y=j;
else
a[nu++]=t;
}
met(tree,);
for(int i=nu-; i>=; i--) {
s+=Sum(a[i]-);
add(a[i],);
}
if(m&)
if(s&)puts("NO");
else puts("YES");
else if(((n-x)^s)&) puts("NO");
else puts("YES");
}
return ;
}