图片说明
图片说明

  • 题意：

  • 给出4*4的矩阵，问你数字拼图能否能复原成原来的样子。

  • 题解：

  • 当逆序对个数的奇偶性和完成时空格所在行和初始时空格所在行的的差奇偶性相同时才有解。

  • 图片说明

  • 代码：

    #include <bits/stdc++.h>
using namespace std;
int a[20];
int main()
{
  int t;
  cin>>t;
  while(t--)
  {
      int k = 0,k2 = 0;
      for(int i=1;i<=4;i++)
      {
          for(int j=1;j<=4;j++)
          {
              cin>>a[i*4+j-4];
              if(a[i*4+j-4] == 0){
                  k = 8-i-j;
                  a[i*4+j-4] = 16;
              }
          }
      }
      for(int i=1;i<16;i++)
      {
          for(int j=i+1;j<=16;j++)
          {
              if(a[j] < a[i]){
                  k2++;
              }
          }
      }
      //cout<<k<<" "<<k2<<endl;
      if(k%2 == k2%2){
          cout<<"Yes"<<endl;
      }else{
          cout<<"No"<<endl;
      }

  }
  return 0;
}