明天蓝桥杯省赛，祝自己好运！！！

本文主要是介绍明天蓝桥杯省赛，祝自己好运！！！，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

蓝桥杯历届试题剪邮票
(DFS)
题目描述
如【图1】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2】，【图3】中，粉红色所示部分就是合格的剪取。

请你计算，一共有多少种不同的剪取方法。

在这里插入图片描述
/*
任何一个点都可以是起点，从12个点中取出5个点，判断一下他们是不是连通就行
下方代码的处理方式是：每取一个数都判断一下这个数是否在之前取那些数的中某个数的上下左右，如果在就true，需要注意的是取得第一个数要直接判断为true，因为在第一个数之前是没有数的。
去重用set嵌套set
*/
解题代码：

#include <iostream>
#include <set>
using namespace std;
int step_x[] = {-1,1,0,0},step_y[] = {0,0,-1,1};
int a[3][4]={1,2,3,4,5,6,7,8,9,10,11,12};
bool used[15];
int v[6];
set<set<int> >ss;
bool check(int now,int cnt)
{if(cnt == 0)return true;int x,y;for(int i = 0; i < cnt; i++){if(v[i] % 4 != 0)//转化该数的在a数组中的index{x = v[i] / 4;y = v[i] % 4 - 1;}else {x = v[i] / 4 - 1;y = 3;}for(int j = 0; j < 4; j++){int xx = x + step_x[j];int yy = y + step_y[j];if(xx>=0&&xx<=2&&yy>=0&&yy<=3){if(a[xx][yy] == now){return true;}}}}return false;
}
void DFS(int cnt)
{if(cnt == 5){set<int>s(v,v+cnt);ss.insert(s);return;}for(int i = 1; i <= 12; i++){if(!used[i] && check(i,cnt)){used[i] = true;v[cnt] = i;DFS(cnt+1);used[i] = false;}}
}int main()
{DFS(0);cout<<ss.size()<<endl;return 0;
}