UVA 129 困难的串Krypton Factor (回溯法)

骑猪看日落 2024-02-17 19:03 110阅读 0赞

#include<cstdio>
const int maxn=80+2;
int S[maxn];
int n,L,count;
void print(int cur){
    int flag=1;
    for(int i=0;i<cur;i++){
        if(i%4==0 && i>0)
        {
            if(i%64==0 && i>0)printf("\n");
            else printf(" ");
        }
        printf("%c",S[i]+'A'); 
    }
    printf("\n%d\n",cur);
}
int dfs(int cur){
    if(count++==n){
    print(cur);  //打印目标字符串 
    return 0; //返回值为0，则表示找到目标串 
    }
    for(int i=0;i<L;i++){  //尝试前L个字母 
        S[cur]=i;
        int ok=1;
        for(int len=1;len<=(cur+1)/2;len++){
            int equal=1;
            for(int j=0;j<len;j++){
                if(S[cur-j]!=S[cur-j-len]){    equal=0;break;}   //检查前一半是否等于后一半 
            }
            if(equal){ok=0;    break;}
        } 
        if(ok){if(!dfs(cur+1))return 0;} //递归搜索，如果已经找到解，则直接退出 
    }
    return 1;
}
int main(){
    while(scanf("%d%d",&n,&L)==2){
        if(n==0 && L==0)break;
        count=0; //表示第n个困难的串 
        dfs(0);
    }
    return 0;
}