P10454 奇数码问题

· · 题解

这道题有点像数字华容道，可以算出两个网格能否能够转化为顺序。

首先，能够任意交换3个数的位置，不能任意交换2个数的位置。 那么则说明能将奇数个数依次替换，偶数则不行，也可以交换偶数次偶数个数。

也就是可以去找所有的环中点数为偶数的环的数量，若两个网格偶环数量的奇偶性相同则可以转换。

可以在最初把0推到右下角。

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
int n,a[505][505],vis[505][505],cnt1,cnt2;
inline int f(){
    pair<int,int>x;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            vis[i][j]=0;
            cin>>a[i][j];
            if(a[i][j]==0)x={i,j};
        }
    }
    for(int i=x.se;i<n;i++){
        a[x.fi][i]=a[x.fi][i+1];
    }
    for(int i=x.fi;i<n;i++){
        a[i][n]=a[i+1][n];
    }a[n][n]=0;
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(!vis[i][j]){
                int u=a[i][j];
                ans^=1;
                do{
                    ans^=1;
                    vis[u/n+1][u%n+1]=1;
                    u=a[u/n+1][u%n+1];
                }while(u!=a[i][j]);
            }
        }
    }return ans;
}
int main(){
    while(cin>>n){
        cnt1=f();
        cnt2=f();

        if(cnt1==cnt2)
            cout<<"TAK\n";
        else 
            cout<<"NIE\n";
    }
    return 0;
}

优化常数:把二维推成一维\ （卡过了输出答案的，实在卡不到最优，而且只比本人第一次交快20ms）：AC

（你可以帮我卡）