首页 > 其他 > 详细

7-5 困难的串

时间:2019-02-03 15:13:11      阅读:243      评论:0      收藏:0      [点我收藏+]

回溯法 

注意return的用法   找到结果了就直接退出dfs  

还有就是数组下标的处理要注意

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

int n,l;
int cnt;
int ans[1000];
int dfs(int cur)
{
    if(cnt++==n)
    {
        for(int i=0;i<cur;i++)
        {
            if(i%4==0&&i>0)
            {
                if(i%64==0)
                     cout<<endl;
                else
                    printf(" ");
            }
            putchar(A+ans[i]);

        }
        printf("\n%d\n",cur);
        return 0;
    }
    for(int i=0;i<l;i++)
    {
        ans[cur]=i;
        int ok=1;
        for(int j=1;j*2<=cur+1;j++)
        {   int equa=1;
            for(int k=0;k<j;k++)
           {
               if(ans[ cur-k ]!=ans[ cur-j-k ]  ){ equa=0;break; }
           }
           if(equa){ok=0;break;}
        }
          if(ok)
                if(!dfs(cur+1))return 0;//用return 0来结束回溯
    }
    return 1;
}


int main()
{
    while(scanf("%d%d",&n,&l)==2&&n&&l)
    {
       
        cnt=0;
        dfs(0);

    }
}

 

7-5 困难的串

原文:https://www.cnblogs.com/bxd123/p/10350370.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!