绝境求生(八数码有解无解的问题,求逆序)

问题 E: 【排序】绝境求生

时间限制: 1 Sec  内存限制: 64 MB
提交: 19  解决: 12

题目描述

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:

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:

The following steps solve the puzzle given above.
 

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

样例输入

复制样例数据

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

结论:N*M矩阵中，若M为奇数->计算给出矩阵的逆序数和与初始状态的逆序数看奇偶性:奇偶相同则存在，反之不存在

                             若M为偶数->计算给出矩阵的逆序数为ans1，初始0所在行与给出的0所在行之间的行间距ans2，判断:

                             （ans1%2） ==（ans2%2）,成立则存在，反之不存在

用树状数组维护

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n, m;
int cnt;
int c[1000005], a[1000005];
int ans;

int lowbit(int x){
	return x & (-x);
}

void add(int x){
	while(x <= cnt){
		c[x]++;
		x += lowbit(x);
	}
}

int sum(int x){
	int su = 0;
	while(x){
		su += c[x];
		x -= lowbit(x);
	}
	return su;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	while(scanf("%d %d", &n, &m) == 2){
		if(!n && !m) break;
		memset(c, 0, sizeof(c));
		int p, x, ans = 0;
		cnt = 0;
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= m; j++){
				scanf("%d", &x);
				if(x == 0) p = n - i;
				else{
					a[cnt++] = x;
				}
			}
		}
		for (int i = cnt - 1; i >= 0; i--){
			ans += sum(a[i]);
			//cout << a[i] << " " <<sum(a[i]) << endl;
			add(a[i]);
		}
		if(m & 1){
			if(ans % 2 == 0){
				printf("YES\n");
			}else{
				printf("NO\n");
			}
			continue;
		}
		if(ans % 2 == p % 2){
			printf("YES\n");
		}else{
			printf("NO\n");
		}
	}

	return 0;
}
/**/