【正经题解】虫食算

$1$ . $DFS$ 深搜
$2$ .可行性剪枝、优化
$3$ .要注意枚举顺序

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n;
bool bo[33];
int map    [33];
int flag;
char a[33],b[33],c[33];
int xx[33];
int swap(char * xx)
{
    for(int i=1;i<=n/2;i++)
    {
        char xxx=xx[i];
        xx[i]=xx[n-i+1];
        xx[n-i+1]=xxx;
    }
}
int pd(int nn)
{
    int t=0;
    for(int i=1;i<=nn;i++)
    {
        int aa=a[i]-'A',bb=b[i]-'A',cc=c[i]-'A';
        if(map[aa]==-1||map[bb]==-1||map[cc]==-1) return 1;
        cc=map[cc];
        int pp=map[aa]+map[bb]+t;
        t=pp/n;
        pp%=n;
        if(pp!=cc)
        {
            return 0;
        }
    }
    return 1;
}
int dfs(int s)
{    
    if(flag) return 1;

    for(int i=1;i<=s;i++)
    {
        int aa=a[i]-'A',bb=b[i]-'A',cc=c[i]-'A';
        aa=map[aa];bb=map[bb],cc=map[cc];
        if(bb!=-1&&cc!=-1&&aa!=-1)
            if((aa+bb)%n!=cc&&(aa+bb+1)%n!=cc) return 0;
        if(bb!=-1&&cc!=-1&&aa==-1)
            if(bo[(cc-bb+n)%n]&&bo[(cc-bb-1+n)%n])
                return 0;
        if(bb==-1&&cc!=-1&&aa!=-1)
            if(bo[(cc-aa+n)%n]&&bo[(cc-aa-1+n)%n])
                return 0;
        if(bb!=-1&&cc==-1&&aa!=-1)
            if(bo[(aa+bb+n)%n]&&bo[(aa+bb+1+n)%n])
                return 0;
    }
    if(!pd(s)) return 0;
    if(s==n)
    {
        if(pd(n)) 
        {
            flag=1;
            for(int i=0;i<n;i++)
                printf("%d ",map[i]);
            return 0;    
        }
        return 0;
    }
    int x=xx[s+1];
    for(int i=n-1;i>=0;i--)
    {
        if(!bo[i])
        {
            bo[i]=1;
            map[x]=i;
            dfs(s+1);
            bo[i]=0;
            map[x]=-1;
        }
    }
}
int main()
{
    memset(map,-1,sizeof(map));
    scanf("%d%s%s%s",&n,a+1,b+1,c+1);
    swap(a);
    swap(b);
    swap(c);
    for(int i=1;i<=n;i++)
    {
        int aa=a[i]-'A',bb=b[i]-'A',cc=c[i]-'A';
        if(!bo[aa])
        {
            xx[++xx[0]]=aa;
            bo[aa]=1;
        }
        if(!bo[bb])
        {
            xx[++xx[0]]=bb;
            bo[bb]=1;
        }
        if(!bo[cc])
        {
            xx[++xx[0]]=cc;
            bo[cc]=1;
        }
    }
    memset(bo,0,sizeof(bo));
    dfs(0);
    
}