P10454 奇数码问题

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

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

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

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

CPP

#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

（你可以帮我卡）

文章操作

相关推荐

评论

P10454 奇数码问题