1671: 数字拼图
时间限制: 1 Sec 内存限制: 16 MB提交: 34 解决: 19
[提交][状态][讨论版]
题目描述
拼图游戏即在任意一个N*N（N>1）的拼图中，会把一张完整的图片裁切成N*N块，去掉尾部一块，然后打乱顺序，通过调换空格块与邻块的位置来还原图片。为了方便计算，我们规定右下角最后一块图片为空，用0代替，其余每一块图片用从1~N*N-1的数字来表示。我们简单示范一下数字拼图的操作吧。
例如3*3的拼图
142
835
670
可以通过0与其他数字横竖交换得到新的拼图
142
830
675
中间可进行无限次0与其他数字的交换。我们最终需要将整张图还原为
123
456
780
我们需要做的就是计算数字拼图还原。是计算还原所需最小的步数吗？当然不是，那对于现在的你们来说还有点困难。我们就从简单的开始吧。首先为了简化操作可以将规定2<=N<=4。
问：任意给一个N*N数字矩阵，能否证明：经过无限次的交换，一定能到达目标矩阵或者经过无限的交换也不能实现目标矩阵？如果能输出YES，如果不能输出NO。
输入
第一行输出N，接下来为（0~N*N-1）的数字矩阵。同行数字间保证有一空格。我们保证一开始0在右下角，且数字符合要求。N为0结束。
输出
如果能还原输出YES，如果不能还原输出NO。
样例输入
3
1 2 3
4 5 6
7 8 0
2
3 2
1 0
0样例输出
YES
NO提示
本题有两种解题思路，一种可以采用模拟解法，将整个过程模拟下来得出答案，另外还可以根据线性代数的逆序数思维求解更简洁。
用逆序数：把矩阵按照从左到右从上到下顺序依次排列，然后查找逆序数是偶数还是奇数，依据逆序数的奇偶性来判断能否还原
#include<bits/stdc++.h>
using namespace std;
const int maxn=100;
int a[maxn][maxn],b[maxn*maxn];
int main()
{
int n,i,j;
while(cin>>n&&n)
{
int k=0;
int sum=0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
cin>>a[i][j];
b[k++]=a[i][j];
}
int K=k;
for(i=0;i<K-1;i++)
{
for(j=i+1;j<K-1;j++) if(b[i]>b[j]) sum+=1;
}
if(b[K-1]==0)
{
if(sum%2!=0) cout<<"NO
";
else cout<<"YES
";
}
else
{
if(sum%2==0) cout<<"NO
";
else cout<<"YES
";
}
}
return 0;
}