蓝桥杯 dfs+剪枝

梦里梦外; 2022-05-29 12:50 173阅读 0赞

#include <cstdio>
    #include <cstring>
    using namespace std;
    int num[15]={0};//数组num[i]表示i这个位置是否占用了
    int vis[8]={0};// 数组用vis[1]~vis[7], 表示数字 1~7 是否已经被使用
    
    //今有7对数字：两个1，两个2，两个3，...两个7，把它们排成一行。
    //要求，两个1间有1个其它数字，两个2间有2个其它数字，以此类推，两个7之间有7个其它数字。
    //如下就是一个符合要求的排列：
    //17126425374635   7 4 1 5 1 6 4 3 7 5 2 3 6 2
    //当然，如果把它倒过来，也是符合要求的。
    //请你找出另一种符合要求的排列法，并且这个排列法是以74开头的。
    void dfs(int step)
    {
        if(step>=14){
    
            for(int i=0;i<14;i++){
                printf("%d%c",num[i],i!=14?' ':'\n');
            }
            return ;
        }
    
        if(num[step]==0){// 先判断这个位是否有数字了 ，如果有了就跳到下一位
    
            for(int i=1;i<=7;i++){
    
                if(vis[i]==0 && num[step+i+1]==0){//关键点，如果i这个数没有被使用，（最关键的）而且要判断出i相应的下一个位置是否被占用了
                        //比如[7][4][3][][][][3][][][][][][][]这种情况，如果下一个是放2，虽然nump[3]==0,
                        //但是由于num[3+2+1]==num[6]==1，即6这个位置已经被前面的某一个数（这里是3）
                        //占用了，所以也就不能再放2了;这里不这样写的话就要很久很久了，所以剪枝很重要
    
                    vis[i]=1;
                    num[step]=i;
                    num[step+i+1]=i;
                    dfs(step+1);
                    vis[i]=0;
                    num[step]=0;
                    num[step+i+1]=0;
                }
            }
    
        }
        else{
    
            dfs(step+1);
        }
    }
    
    int main ()
    {
         // 初始化 74 开头
        vis[4]=1;
        vis[7]=1;
        num[0]=4;
        num[1]=7;
        num[6]=4;
        num[8]=7;
        dfs(2);
    	return 0;
    }