Odd number problem

描述

你一定玩过八数码游戏，它实际上是在一个3*3的网格中进行的，1个空格和1~8这8个数字恰好不重不漏地分布在这3*3的网格中。
例如：
5 2 8
1 3 _
4 6 7
在游戏过程中，可以把空格与其上、下、左、右四个方向之一的数字交换（如果存在）。
例如在上例中，空格可与左、上、下面的数字交换，分别变成：
5 2 8       5 2 _      5 2 8
1 _ 3       1 3 8      1 3 7
4 6 7       4 6 7      4 6 _

奇数码游戏是它的一个扩展，在一个n*n的网格中进行，其中n为奇数，1个空格和1~n*n-1这n*n-1个数恰好不重不漏地分布在n*n的网格中。
空格移动的规则与八数码游戏相同，实际上，八数码就是一个n=3的奇数码游戏。

现在给定两个奇数码游戏的局面，请判断是否存在一种移动空格的方式，使得其中一个局面可以变化到另一个局面。

输入格式

多组数据，对于每组数据：
第1行一个整数n，n<500，n为奇数。
接下来n行每行n个整数，表示第一个局面。
接下来n行每行n个整数，表示第二个局面。
局面中每个整数都是0~n*n-1之一，其中用0代表空格，其余数值与奇数码游戏中的意义相同，保证这些整数的分布不重不漏。

输出格式

对于每组数据，若两个局面可达，输出TAK，否则输出NIE。

样例输入

3 1 2 3 0 4 6 7 5 8 1 2 3 4 5 6 7 8 0 1 0 0

样例输出

TAK TAK

 #include<cstdio>

 //#include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<vector>

 //#include<queue>

 //#include<set>

 #define INF 0x3f3f3f3f

 #define N 250005

 #define re register

 #define Ii inline int

 #define Il inline long long

 #define Iv inline void

 #define Ib inline bool

 #define Id inline double

 #define ll long long

 #define Fill(a,b) memset(a,b,sizeof(a))

 #define R(a,b,c) for(register int a=b;a<=c;++a)

 #define nR(a,b,c) for(register int a=b;a>=c;--a)

 #define Min(a,b) ((a)<(b)?(a):(b))

 #define Max(a,b) ((a)>(b)?(a):(b))

 #define Cmin(a,b) ((a)=(a)<(b)?(a):(b))

 #define Cmax(a,b) ((a)=(a)>(b)?(a):(b))

 #define D_e(x) printf("\n&__ %d __&\n",x)

 #define D_e_Line printf("-----------------\n")

 #define D_e_Matrix for(re int i=1;i<=n;++i){for(re int j=1;j<=m;++j)printf("%d ",g[i][j]);putchar('\n');}

 using namespace std;

 //    The Code Below Is Bingoyes's Function Forest.

 Ii read(){

     int s=,f=;char c;

     for(c=getchar();c>''||c<'';c=getchar())if(c=='-')f=-;

     while(c>=''&&c<='')s=s*+(c^''),c=getchar();

     return s*f;

 }

 Iv print(ll x){

     if(x<)putchar('-'),x=-x;

     if(x>)print(x/);

     putchar(x%^'');

 }

 /*

 Iv Floyd(){

     R(k,1,n)

         R(i,1,n)

             if(i!=k&&dis[i][k]!=INF)

                 R(j,1,n)

                     if(j!=k&&j!=i&&dis[k][j]!=INF)

                         Cmin(dis[i][j],dis[i][k]+dis[k][j]);

 }

 Iv Dijkstra(int st){

     priority_queue<int>q;

     R(i,1,n)dis[i]=INF;

     dis[st]=0,q.push((nod){st,0});

     while(!q.empty()){

         int u=q.top().x,w=q.top().w;q.pop();

         if(w!=dis[u])continue;

         for(re int i=head[u];i;i=e[i].nxt){

             int v=e[i].pre;

             if(dis[v]>dis[u]+e[i].w)

                 dis[v]=dis[u]+e[i].w,q.push((nod){v,dis[v]});

         }

     }

 }

 Iv Count_Sort(int arr[]){

     int k=0;

     R(i,1,n)

         ++tot[arr[i]],Cmax(mx,a[i]);

     R(j,0,mx)

         while(tot[j])

             arr[++k]=j,--tot[j];

 }

 Iv Merge_Sort(int arr[],int left,int right,int &sum){

     if(left>=right)return;

     int mid=left+right>>1;

     Merge_Sort(arr,left,mid,sum),Merge_Sort(arr,mid+1,right,sum);

     int i=left,j=mid+1,k=left;

     while(i<=mid&&j<=right)

         arr[i]<=arr[j]?

             tmp[k++]=arr[i++]:

             tmp[k++]=arr[j++],sum+=mid-i+1;//Sum Is Used To Count The Reverse Alignment

     while(i<=mid)tmp[k++]=arr[i++];

     while(j<=right)tmp[k++]=arr[j++];

     R(i,left,right)arr[i]=tmp[i];

 }

 Iv Bucket_Sort(int a[],int left,int right){

     int mx=0;

     R(i,left,right)

         Cmax(mx,a[i]),++tot[a[i]];

     ++mx;

     while(mx--)

         while(tot[mx]--)

             a[right--]=mx;

 }

 */

 int n,m,a[N],tmp[N];

 Iv Merge_Sort(int arr[],int left,int right,int &sum){

     if(left>=right)return;

     int mid=left+right>>;

     Merge_Sort(arr,left,mid,sum),Merge_Sort(arr,mid+,right,sum);

     int i=left,j=mid+,k=left;

     while(i<=mid&&j<=right)

         (arr[i]<=arr[j])?

             tmp[k++]=arr[i++]:

             (tmp[k++]=arr[j++],sum+=mid-i+);//Sum Is Used To Count The Reverse Alignment

     while(i<=mid)tmp[k++]=arr[i++];

     while(j<=right)tmp[k++]=arr[j++];

     R(i,left,right)arr[i]=tmp[i];

 }

 #define PutTAK printf("TAK\n")

 #define PutNIE printf("NIE\n")

 int main(){

     int n;

     while(scanf("%d",&n)!=EOF){

         int sum_start=,sum_end=;

         n*=n;

         if(!n)

             PutNIE;

                             //Judge Case Of n=0 Specially

         if(n==){

             (read()==read())?

                 PutTAK:

                 PutNIE;

             continue;

         }                    //Judge Case Of n=1 Specially

         int cnt_num=;

         R(i,,n){

             int num=read();

             if(num)

                 a[++cnt_num]=num;

         }

         Merge_Sort(a,,cnt_num,sum_start);

         cnt_num=;

         R(i,,n){

             int num=read();

             if(num)

                 a[++cnt_num]=num;

         }

         Merge_Sort(a,,cnt_num,sum_end);

         ((sum_start&)==(sum_end&))?

             PutTAK:

             PutNIE;

     }

     return ;

 }

 /*

     Note:

     Error:

 */