题目描述
所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：
43#9865#045
+ 8468#6633
44445506978
其中#号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是5和3，第二行的数字是5。
现在，我们对问题做两个限制：
首先，我们只考虑加法的虫食算。这里的加法是N进制加法，算式中三个数都有N位，允许有前导的0。
其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。如果这个算式是N进制的，我们就取英文字母表午的前N个大写字母来表示这个算式中的0到N-1这N个不同的数字：但是这N个字母并不一定顺序地代表0到N-1)。输入数据保证N个字母分别至少出现一次。
BAD+ CRDADCCC
上面的算式是一个4进制的算式。很显然，我们只要让ABCD分别代表0123，便可以让这个式子成立了。你的任务是，对于给定的N进制加法算式，求出N个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解
输入描述:
输入包含4行。
第一行有一个正整数，后面的3行每行有一个由大写字母组成的字符串，分别代表两个加数以及和。这3个字符串左右两端都没有空格，从高位到低位，并且恰好有N位
输出描述:
输出包含一行。在这一行中，应当包含唯一的那组解。解是这样表示的：输出N个数字，分别表示A，B，C……所代表的数字，相邻的两个数字用一个空格隔开，不能有多余的空格
示例1
输入
5
ABCED
BDACE
EBBAA
输出
1 0 3 4 2
备注
对于30％的数据，保证有；
对于50％的数据，保证有；
对于全部的数据，保证有。
解答
此题明显为深搜在此不再赘述，搜索的主要思想是减小搜索树，所以实现方法如下
1.从后往前，从上往下搜，避免后位进位的麻烦。
2.每次搜完update一遍map，然后再判断是否已经有不合法情况出现：一列三个已知不合法，例如1+1=3；已知两个数未知进位但 进不进都不可以满足就不合法；一列已知两个数以及进位计算后不合法。这三种情况直接return（如果实在看不懂请见代码的judge函数）
3.在搜一个数时如果所有情况都失败则return（没什么好讲的，但问题在于我就卡死在这了。。。）
4.一列已知两个数及进位情况就直接算第三个数 ！！且不满足时直接return！！（手动标红）
5.一列已知两个数未知进位只要搜进位的或不进位的。（这我懒得加。。。）
6.个人认为每次把map上面的数换来换去太烦了，所以定义了一个r数组存放代换规则。
代码：#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int map[10][50];//单纯的map
int r[50];//代换规则
bool used[50],flag=1;//是否用过 是否出解
int ad[50];//明确的进位情况
int n;
bool judge()//判断是否有不合法情况，有则return false。
{
int add=0,i;
for(i=n;i>=1;i--)
{
if(r[map[1][i]]!=-1&&r[map[2][i]]!=-1&&r[map[3][i]]!=-1)
{
if(add==-1&&(r[map[1][i]]+r[map[2][i]])%n!=r[map[3][i]]&&(r[map[1][i]]+r[map[2][i]]+1)%n!=r[map[3][i]])
return false;
if(add!=-1)
{
if((r[map[1][i]]+r[map[2][i]]+add)%n==r[map[3][i]]) add=(r[map[1][i]]+r[map[2][i]]+add)/n;
else return false;
}
}
else add=-1;
}
return true;
}
int find(int i,int y)//第四条
{
if(y==1)
{
if(r[map[2][i]]!=-1&&r[map[3][i]]!=-1)
{
int tmp=(r[map[3][i]]+n-r[map[2][i]])%n;
if(ad[i+1]==1) tmp=(tmp-1+n)%n;
if(used[tmp]==0)
return tmp;
else return -2;
}
return -1;
}
else if(y==2)
{
if(r[map[1][i]]!=-1&&r[map[3][i]]!=-1)
{
int tmp=(r[map[3][i]]+n-r[map[1][i]])%n;
if(ad[i+1]==1) tmp=(tmp-1+n)%n;
if(used[tmp]==0)
return tmp;
else return -2;
}
return -1;
}
else if(y==3)
{
if(r[map[1][i]]!=-1&&r[map[2][i]]!=-1)
{
int tmp=(r[map[1][i]]+r[map[2][i]])%n;
if(ad[i+1]==1) tmp=(tmp+1)%n;
if(used[tmp]==0)
return tmp;
else return -2;
}
return -1;
}
}
void updatead()//更新进位器
{
int i;
for(i=n;i>=1;i--)
if(r[map[1][i]]!=-1&&r[map[2][i]]!=-1&&ad[i+1]!=-1)
{
if(r[map[1][i]]+r[map[2][i]]+ad[i+1]>=n)
ad[i]=1;
else ad[i]=0;
}
else return;
return;
}
void dfs(int step,int x)//以确定的字母数 搜索到哪里了
{
int i,j,k;
if(!judge()) return;//判断
updatead();//更新
if(step==n) {for(i=1;i<=n;i++) printf("%d ",r[i]);flag=0; return;}//出解
for(i=x;i>=1;i--)
{
for(j=1;j<=3;j++)
if(r[map[j][i]]==-1)//正常情况
{
int tmp=find(i,j);
if(tmp==-1)
{
for(k=n-1;k>=0;k--)
if(used[k]==0)
{
used[k]=1;
r[map[j][i]]=k;
dfs(step+1,i);
if(flag==0) return;
r[map[j][i]]=-1;
used[k]=0;
}
return;//特别注意
}
else if(tmp==-2) return;//已不合法
else //推出来的情况
{
used[tmp]=1;
r[map[j][i]]=tmp;
dfs(step+1,i);
r[map[j][i]]=-1;
used[tmp]=0;
return;//特别注意
}
}
}
}
int main()
{
int i;
string s1,s2,s3;
memset(r,-1,sizeof(r));
memset(ad,-1,sizeof(ad));
scanf("%d\n",&n);
ad[n+1]=0;
cin>>s1>>s2>>s3;
for(i=0;i<n;i++) map[1][i+1]=s1[i]-'A'+1;
for(i=0;i<n;i++) map[2][i+1]=s2[i]-'A'+1;
for(i=0;i<n;i++) map[3][i+1]=s3[i]-'A'+1;
dfs(0,n);
return 0;
} 来源：Function_Endless
京公网安备 11010502036488号