题目描述

所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：

43#9865#045

    +     8468#6633

      44445506978

其中#号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是5和3，第二行的数字是5。

现在，我们对问题做两个限制：

首先，我们只考虑加法的虫食算。这里的加法是N进制加法，算式中三个数都有N位，允许有前导的0。

其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。如果这个算式是N进制的，我们就取英文字母表午的前N个大写字母来表示这个算式中的0到N-1这N个不同的数字：但是这N个字母并不一定顺序地代表0到N-1)。输入数据保证N个字母分别至少出现一次。

 BADC

       +   CRDA

            DCCC

上面的算式是一个4进制的算式。很显然，我们只要让ABCD分别代表0123，便可以让这个式子成立了。你的任务是，对于给定的N进制加法算式，求出N个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解

输入描述:

输入包含4行。
第一行有一个正整数N(N<=26)，后面的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