首页 > 代码库 > uva129 - Krypton Factor 7.4.3 困难的串

uva129 - Krypton Factor 7.4.3 困难的串

2024-07-08 16:45:21   212人阅读

 

7.4.3困难的串

学习点：dfs加入返回值，递归搜索过程中如果有一个成功，就直接退出

//7.4.3 困难的串#include<cstdio>#include<cstring>#include<iostream>#include<string>#include<algorithm>using namespace std;int n,L;int cnt;char v[81];bool judge(int cur){    for(int i=1;i<=(cur+1)/2;i++)//判断长度为2*i的后缀是否有相同的    {        bool equal=1;        for(int j=0;j<i;j++)            if(v[cur-i-j]!=v[cur-j])              {                equal=0;                break;            }        if(equal)            return false;    }    return true;}int dfs(int cur){    //printf("cur: %d\n", cur);    for(int i=0;i<L;i++)    {        v[cur]=‘A‘+i;        if(judge(cur))        {            cnt++;            if(cnt==n)            {                v[cur+1]=0;                printf("%s\n", v);                return 1;            }            if(dfs(cur+1))                return 1;        }    }    return 0;}int main(){    while(cin>>n>>L)    {        cnt=0;        dfs(0);        }    return 0;}

修改一下输出格式即可解决uva129

//7.4.3 困难的串#include<cstdio>#include<cstring>#include<iostream>#include<string>#include<algorithm>using namespace std;int n,L;int cnt;char v[81];bool judge(int cur){    for(int i=1;i<=(cur+1)/2;i++)//判断长度为2*i的后缀是否有相同的    {        bool equal=1;        for(int j=0;j<i;j++)            if(v[cur-i-j]!=v[cur-j])              {                equal=0;                break;            }        if(equal)            return false;    }    return true;}void output(int cur){    for(int i=0;i<=cur;i++)    {        if(i%4==0 && i>0)        {            if(i%64==0 && i>0)                putchar(‘\n‘);            else                putchar(‘ ‘);        }        putchar(v[i]);    }    printf("\n%d\n", cur+1);}int dfs(int cur){    //printf("cur: %d\n", cur);    for(int i=0;i<L;i++)    {        v[cur]=‘A‘+i;        if(judge(cur))        {            cnt++;            if(cnt==n)            {                v[cur+1]=0;                //printf("%s\n", v);                output(cur);                return 1;            }            if(dfs(cur+1))                return 1;        }    }    return 0;}int main(){    while(cin>>n>>L && n && L)    {        cnt=0;        dfs(0);        }    return 0;}


联系
我们