题目链接
解题思路
好题啊！这个搜索好难写......
大概是要考虑进位和考虑使用过某个数字这两个东西，但就很容易出错......
首先这个从后往前搜比较好想，按照从后往前出现的顺序搜，在这个剪枝条件下速度会快很多。
比如样例，
5
ABCED
BDACE
EBBAA
从右往左出现的次序是\(DEAECACABBDBABE\)，去重之后是\(DEACB\)，这就是要搜索的顺序，用\(seq\)记录。
当某时候等式明显已经不满足时，就直接\(return\)。
还有别的剪枝，但这样直接能\(79ms\)。没必要。
AC代码
#include<stdio.h>
#include<stdlib.h>
#define N 30
int n,a[N],b[N],c[N],vis[N],ans[N];
char s[3][N];
int seq[N];//搜索顺序
void dfs(int x){//搜到第x个元素
int i,jw=0;
if(ans[a[0]]+ans[b[0]]>=n)return;
for(i=n-1;i>=0;i--){//从后往前检查
int A=ans[a[i]],B=ans[b[i]],C=ans[c[i]];
if(A==-1||B==-1||C==-1)continue;
if((A+B+1)%n!=C&&(A+B)%n!=C)return;
}
if(x==n){
for(i=n-1;i>=0;i--){
int A=ans[a[i]],B=ans[b[i]],C=ans[c[i]];
if((A+B+jw)%n!=C)return;
jw=(A+B+jw)/n;
}
for(i=0;i<n;i++)printf("%d ",ans[i]);
exit(0);
}
for(i=n-1;i>=0;i--){
if(!vis[i]){
vis[i]=1;ans[seq[x]]=i;
dfs(x+1);
vis[i]=0;ans[seq[x]]=-1;
}
}
}
int cnt;
void f(int x){//提供搜索顺序，加快搜索速度
if(!vis[x]){vis[x]=1;seq[cnt++]=x;}
}
int main(){
int i;
for(i=0;i<30;i++)ans[i]=-1;
scanf("%d%s%s%s",&n,s[0],s[1],s[2]);
for(i=0;i<n;i++){
a[i]=s[0][i]-'A';
b[i]=s[1][i]-'A';
c[i]=s[2][i]-'A';
}
for(i=n-1;i>=0;i--){f(a[i]);f(b[i]);f(c[i]);}
for(i=0;i<n;i++)vis[i]=0;
dfs(0);
return 0;
}
这是seq优化后的结果：
这是从n-1到1搜索的结果：
而这是从1到n-1搜索的结果：
