AcWing 184. 虫食算
原题链接
简单
作者:
sy123
,
2021-02-05 01:57:29
,
所有人可见
,
阅读 454
#include<bits/stdc++.h>
using namespace std;
const int N=30;
char e[4][N];
bool vis[N];
int path[N];//每个字母填什么
int n;
void dfs(int x,int y,int t){
for(int i=n-1;i>=0;i--){
int a1=path[e[0][i]-'A'],b1=path[e[1][i]-'A'],c1=path[e[2][i]-'A'];
if(a1!=-1&&b1!=-1&&c1!=-1){
if((a1+b1)%n!=c1&&(a1+b1+1)%n!=c1)return;
}
}
if(y==-1){
if(t==0){
for(int i=0;i<n;i++)
cout<<path[i]<<' ';
}
exit(0);
}
int c=e[x][y]-'A';
if(x<2){
if(path[c]==-1){
for(int i=0;i<n;i++){
if(!vis[i]){
path[c]=i;
vis[i]=true;
dfs(x+1,y,t);
path[c]=-1;
vis[i]=false;
}
}
}
else{
dfs(x+1,y,t);
}
}
else{
int a=path[e[0][y]-'A'],b=path[e[1][y]-'A'];
t+=a+b;
if(path[c]!=-1&&t%n==path[c]){
dfs(0,y-1,t/n);
}
if(path[c]==-1&&!vis[t%n]){//c没被赋值
path[c]=t%n;
vis[t%n]=true;
dfs(0,y-1,t/n);
path[c]=-1;
vis[t%n]=false;
}
}
}
int main(){
cin>>n>>e[0]>>e[1]>>e[2];
memset(path,-1,sizeof path);
dfs(0,n-1,0);
return 0;
}