POJ - 2893 M × N Puzzle 奇数码问题升级
题目描述
给定n * m的图，问是否可以达到最终态
可以 输出YES
不可以 输出NO
样例
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
思路
考虑m为奇数的情况，空格往前后移动，逆序对的数量不变，当它往上下移动的时候，收到影响的是它的前m-1个数，m-1为偶数，所以当最后的状态逆序对和开始逆序对的奇偶不同时，就不能到达 m为偶数时，m-1为奇数， 所以上下移动一次，奇偶性会改变一次，所以：当前逆序对数量与最后的逆序对数量的差的奇偶性，与两个状态的空格所在行数的差奇偶性相同时，他们可以到达，不然不行代码
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N = 1000010;
int a[N], b[N];
int n, m;
int t[N];
int merge_sort(int *a, int l, int r)
{
if (l >= r)
return 0;
int mid = (l + r) >> 1;
int i = l, j = mid + 1, k = 0;
int ans = 0;
ans += merge_sort(a, l, mid) + merge_sort(a, mid + 1, r);
while (i <= mid && j <= r)
{
if (a[i] <= a[j])
t[++k] = a[i++];
else
{
t[++k] = a[j++];
ans += mid - i + 1;
}
}
while (i <= mid)
t[++k] = a[i++];
while (j <= r)
t[++k] = a[j++];
for (int i = l, j = 1; i <= r; i++)
{
a[i] = t[j++];
}
return ans;
}
int main()
{
while(scanf("%d%d", &n, &m) != EOF)
{
if( n == 0 && m == 0)
break;
int k = 0;
int fi, se;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
int x;
scanf("%d", &x);
if(x != 0)
a[++k] = x;
else fi = i;
}
se = n;
int aa = merge_sort(a, 1, n * m - 1);
int bb = 0;
if(m & 1)
{
if(aa & 1)
printf("NO\n");
else printf("YES\n");
}
else{
int t = n - fi;
int tt = aa;
if((t - tt) & 1)
printf("NO\n");
else printf("YES\n");
}
}
return 0;
}
作者：正月看雪花
