提出 #49299739

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define int long long 
using namespace std;
inline int read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+(ch^48);
		ch=getchar(); 
	}
	return x;
}
const int p1=998244353,p2=1e9+7,N=131,INF=1e9;
int n,m,ans=INF,a[10][10],b[10][10];
map<pair<int,int>,int> mp,vis; 
vector<int> vec;
inline pair<int,int> calc(){
	int s1=0,s2=0;
	for(auto x:vec){
		s1=(s1*N+x)%p1;
		s2=(s2*N+x)%p2;
	}
	return make_pair(s1,s2);
}
inline void rotate(int x,int y){
	for(int i=1;i<n;i++){
		for(int j=1;j<m;j++){
			int ti=(n-i),tj=(m-j);
			if((i*m+j)<=(ti*m+tj)) continue;
			swap(a[i+x][j+y],a[ti+x][tj+y]);
		}
	}
	return;
} 
void dfs1(int x){
	if(x>10) return;
	vec.clear();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) vec.push_back(a[i][j]); 
	}
	pair<int,int> N=calc();
	if(!vis[N]){
		vis[N]=1,mp[N]=x;
	}else{
		mp[N]=min(mp[N],x);
	}
	for(int i=0;i<=1;i++){
		for(int j=0;j<=1;j++){
			rotate(i,j);
			dfs1(x+1);
			rotate(i,j);
		}
	}
	return;
}
void dfs2(int x){
	if(x>10) return;
	vec.clear();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) vec.push_back(a[i][j]);
	}
	pair<int,int> N=calc();
	if(vis[N]) ans=min(ans,x+mp[N]);
	for(int i=0;i<=1;i++){
		for(int j=0;j<=1;j++){
			rotate(i,j);
			dfs2(x+1);
			rotate(i,j);
		}
	}
	return;
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			a[i][j]=read();
		}
	}
	dfs1(0);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			a[i][j]=(i-1)*m+j;
		}
	}
	dfs2(0);
	printf("%lld\n",(ans==INF)?-1:ans);
	return 0;
} 

提出情報

ジャッジ結果