POJ - 2893 M × N Puzzle 奇数码问题升级

Nadia ·

更新时间:2024-09-20

· 874 次阅读

题目描述

给定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;
}

作者：正月看雪花

poj 数码

1024 个赞