提供一个简洁的做法
查看原帖
提供一个简洁的做法
49920
蹲在丛中笑楼主2020/12/4 20:28

(这个代码是我好几年前写的,由于没有剪枝一直T一个点,到今天开O2才过了

就是从右向坐一列列枚举这三位的字母是什么,如果和之前重复了就回溯

这里我是从大到小枚举的,这样枚举结束的标志就是-1

之所以要发题解,是因为代码中用了大量的goto,可以在这里看到goto的巧妙应用,极大地压缩了代码的长度

#include<cstdio>
#include<cstdlib>
int n,w[27],v[27];
char a[27],b[27],c[27];//w是ABCD..等字母分别对应的数字,v是0123..等数字是否已经被访问
void dfs(int u,int d) { //u是列编号,d是进位的数字
    if (u<0) { if (d==0) { for (int i=0;i<n;++i) printf("%d ",w[i]); exit(0); } return; }
    int x,y,z,t,&wa=w[a[u]],&wb=w[b[u]],&wc=w[c[u]];
    if ((x=wa)==-1) wa=n;
    xxx:
        if (x==-1) { do if (--wa<0) goto xx; while (v[wa]); v[wa]=1; }
        if ((y=wb)==-1) wb=n;
        yyy:
            if (y==-1) { do if (--wb<0) goto yy; while (v[wb]); v[wb]=1; }
                t=(wa+wb+d)%n;
                if ((z=wc)==-1&&!v[t]) v[t]=1,wc=t;
                    if (t==wc) dfs(u-1,(wa+wb+d)/n); //这里进入下一层递归
                if (z==-1&&wc!=-1) v[wc]=0,wc=-1;
            if (y==-1) { v[wb]=0; goto yyy; } // y==-1意味着当前层之前w[b[u]]这个字母之前没有被赋值,因而可以继续枚举它的值
        yy:
        if (x==-1) { v[wa]=0; goto xxx; } //同“y==-1”的注释
    xx:;
}
signed main() {
    scanf("%d%s%s%s",&n,a,b,c);
    for (int i=0;i<n;++i) a[i]-=65,b[i]-=65,c[i]-=65,w[i]=-1;
    dfs(n-1,0);
}
2020/12/4 20:28
加载中...