虫食算
解题思路
dfs
依次枚举每个字母表示的数字
手动加法竖式(从右到左)
判断实现
1. 从后往前枚举每一列,x,y,z为别为加数,加数,和。如果右边的所有数都确定了,则当前的进位也确定,用o表示,如果x+y+o≠z,就不合法
2. 如果右边存在一些数不确定,则上一位的进位可能是0或1,那么如果x+y≠z,x+y+1≠z同时成立,也是不合法的
3. 对于最高位,如果有进位,也不合法(因为和也为n位数)
AC代码
#include<cstring>
#include<cstdio>
using namespace std;
int n,tot,c[30],cc[30],ans[30];
char a[30],s[5][30];
bool check()///判断
{
int o=0;
for(int i=n;i>=1;i--)
{
int x=ans[s[1][i]-65],y=ans[s[2][i]-65],z=ans[s[3][i]-65];
if(x!=-1&&y!=-1&&z!=-1)
{
if(o!=-1)
{
if((x+y+o)%n!=z)return 0;
if(i==1&&x+y+o>=n)return 0;
o=(x+y+o)/n;
}
else
{
if((x+y+0)%n!=z&&(x+y+1)%n!=z)return 0;
if(i==1&&x+y>=n)return 0;
}
}
else o=-1;
}
return 1;
}
bool dfs(int x)//搜索
{
if(x==tot+1)return 1;
for(int i=0;i<n;i++)
if(cc[i]==0)
{
ans[a[x]-65]=i;
cc[i]=1;
if(check()&&dfs(x+1))return 1;
ans[a[x]-65]=-1;
cc[i]=0;
}
return 0;
}
int main()
{
memset(ans,-1,sizeof(ans));//初值
scanf("%d",&n);//输入
for(int i=1;i<=3;i++)
scanf("%s",s[i]+1);
for(int j=n;j>=1;j--)
for(int i=1;i<=3;i++)
if(c[s[i][j]-65]==0)
{
c[s[i][j]-65]=1;
a[++tot]=s[i][j];
}
dfs(1);
for(int i=0;i<n;i++)
printf("%d ",ans[i]);
return 0;
}