虫食算

题意:现在有N进制的数,现在从A到往后数N-1个每一个字母都代表0~N-1当中的一个数字,现在给你三行字母,相当于第一行字母组合代表一个数字,第二行字母组合代表一个数字,第三行字母组合代表一个数字即是前两行字母代表的数字的和。现在规定每个数字只能有一个字母代表,即一个字母只能代表一个数字,现在让你根据这三行字母求出每个字母代表的数字是多少。

思路:暴力搜索+剪枝。从第n列第一行开始往下搜索,遵循从左到右从上到下的搜索原则。搜索边界则是第0列。则如何判断搜索到搜索边界的时候当前枚举的所有数字字母对是否正确。根据题意三行的字母长度都是相同的,即枚举到第一列第3行字母是哪个数字时,在往下枚举到第0列的时候是不应该有进位的,如果有,则第三行的长度会大于前两行。另外如何剪枝,每枚举到一列的时候,就判定一下是否有继续向左边的列枚举的必要,即右边的列枚举过的字母数字对,在左边任然又可能出现,所以如果出现了,就要判断它所在的那一列如果三个数字群斗枚举过了,是否满足第一行的数字+第二行的数字=第三行的数字,如果不满足,证明,枚举的方案是错误的,直接结束。

出现的错误:递归边界只给满足解存在的if语句加了return 语句,如果不满足if条件,则就一直停在递归边界结束不了了。

                     每一层dfs中,t  都是要被反复运用的,我直接把它在某一个枚举方案中给改了,然后直接传给下一层dfs,这样的话,当前dfs层当中 t 的值改变了,而别的枚举方案还要用到它,肯定就出错 了。 w 这个值也出现相同的错误 ,直接把它给在某一处给 改变了传给下一层,而忽视了它在当前层别的枚举方案中还要用。

                    明明是第一行+第二行数字!=第三行数字 与 第一行数字+ 第二行数字 +进位!=第三行数字 时 证明当前方案不合法,我却把&&写成了   ||  

插入代码:还有这道题的题解说是枚举每个字母对应的数字的时候数字从大到小枚举,程序效率会更高,我不清楚为什么数字从小到大枚举效率就会低,谁能留言指出么

#include<bits/stdc++.h>
using namespace std;

int flag[30];
char s[4][30];
int N;
int use[30];
int id(char op)
{
    return op-'A'+1;
}

void dfs(int x,int y,int t)
{
    if(y==0)
    {
        if(t==0)
        {
           for(int i=1;i<=N;i++)
           {
               cout<<flag[i]<<" ";
           }
           return ;
        }
        return ;
    }

    for(int i=y-1;i>=1;i--)
    {
        int w1=flag[id(s[1][i])];
        int w2=flag[id(s[2][i])];
        int w3=flag[id(s[3][i])];
        if(w1==-1||w2==-1||w3==-1)
            continue;
        else if((w1+w2)%N!=w3&&(w1+w2+1)%N!=w3)
        return ;
    }

    if(flag[id(s[x][y])]==-1)
    {
        for(int i=N-1;i>=0;i--)
        {
            if(!use[i]){
                if(x==3)
                {
                    int w=flag[id(s[1][y])]+flag[id(s[2][y])]+t;
                    if(w%N!=i) continue;
                    use[i]=1;flag[id(s[x][y])]=i;dfs(1,y-1,w/N);use[i]=0;
                    flag[id(s[x][y])]=-1;
                }
                else if(x!=3)
                {
                    use[i]=1;
                    flag[id(s[x][y])]=i;
                    dfs(x+1,y,t);
                    use[i]=0;
                    flag[id(s[x][y])]=-1;
                }
            }
        }
    }
    else if(flag[id(s[x][y])]!=-1)
    {
        if(x!=3)
            dfs(x+1,y,t);
        else if(x==3)
        {
           int w=flag[id(s[1][y])]+flag[id(s[2][y])]+t;
           if(w%N!=flag[id(s[x][y])]) return ;
           else{dfs(1,y-1,w/N);}
        }
    }

}

int main()
{
    cin>>N;
    for(int i=1;i<=3;i++)
        scanf("%s",s[i]+1);
        memset(flag,-1,sizeof flag);
    dfs(1,N,0);
    return 0;
}
原文地址:https://www.cnblogs.com/rainyskywx/p/11043091.html