第七届蓝桥杯省赛大学B组C/C++---剪邮票---DFS

第七届其他题目解析

题目

求共有几种方案

答案是116

这个题呢 参考了网上的思路 很巧妙
我们从12个数中拿出5个不重复的数 我们找出所有的情况
然后dfs判断情况是否符合题意（5个数是否联通）
ps：注意一个小技巧 我们在dfs判断联通的时候 我们从一个点出发，要判断他的上下左右能不能走，观察这个图 我们会发现，上下的数字差是4 左右的数字差是1 那我们只要判断差是不是1或4 就知道能不能走了。但是还有一个特殊情况，4和5的差是1，但是4并不能走到5。怎么解决这个问题呢，我们重新构造一个图

因为我们目的是判断连通性，那么我们关注的是各个点的相对位置，才能判断是否联通。所以数字的大小其实无所谓，所以我们构造出来的这个图，上下的差是5，左右的差是1。我们只需要判断两个数的差是不是5和1.就可以直到是否联通了。

代码及注释

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
int f[5];
int cnt=0;
int v[5];
void dfs(int n){
    v[n]=1;//标记联通
    for(int i=0;i<5;i++){
        if(!v[i]){
            if(abs(f[i]-f[n])==1)dfs(i);
            if(abs(f[i]-f[n])==5)dfs(i);
        }
    }
}
int main(){
    int x[12]={1,2,3,4,6,7,8,9,11,12,13,14};
    for(int a=0;a<8;a++){
        for(int b=a+1;b<9;b++){
            for(int c=b+1;c<10;c++){
                for(int d=c+1;d<11;d++){
                    for(int e=d+1;e<12;e++){
                        f[0]=x[a];f[1]=x[b];
                        f[2]=x[c];f[3]=x[d];f[4]=x[e];

                        memset(v,0,sizeof(v));//清0标记数组
                        dfs(0);

                        //判断5个数是否联通
                        int sum=0;
                        for(int i=0;i<5;i++)sum+=v[i];
                        if(sum==5)cnt++;
                    }
                }
            }
        }
    }

    printf("%d\n",cnt);

    return 0;
}