2016年蓝桥杯省赛C/C++ A组-剪邮票

题目

如下图，有12张连在一起的12生肖的邮票。

现在你要从中剪下5张来，要求必须是连着的。 （仅仅连接一个角不算相连）

比如，粉红色所示部分就是合格的剪取。

题解

全排列+递归 或 DFS+递归。

与2013年的剪格子几乎一样，但是13年的剪格子由于数据比较特殊，所以纯DFS就可以AC，但是其本质与本题是相同的，如果真正正确，那么不能纯DFS。

纯DFS只能实现依次遍历，即S型遍历，但是无法实现T型遍历，而本题很显然存在T型连通的情况，因此纯DFS遍历失效。

DFS的整体思路： 从这12个数中选取5个数（用dfs），判断选取的5个数是否满足全部连通（递归），如果满足则答案数加一，不满足就选取另外的5个数。

DFS实现从N个数中选M个数

DFS判断二维空间中是否连通

全排列的话不能对1~12进行全排列，因为全排列的本质是A(n,m)，也就是说选出的m个数是有序的，这与题目的要求是不符的。因为我们需要在12个数中5个数，所以我们要对包含7个0和5个1的数组进行全排列，每个数的下标就是该数，1表示选该数，0表示不选该数。

对于每种情况，采用的递归的方法判断一下连通性。

代码 DFS

#include
using namespace std;
const int N = 100;

int n = 3, m = 4, K = 5;
int vis[N], used[N];
int ans;

int getsum (int x, int y) { // 这个函数必须要传入行号和列号，不能传入降维至一维的编号 
	if (x = n || y = m) return 0; // 如果用一维坐标算出x和y，那么一定不会存在id%m>=m的情况，这是因为一维编号对应的可能是个非法位置的二维坐标 
	if (used[x*m+y]) return 0;
	if (!vis[x*m+y]) return 0;
	
	used[x*m+y] = 1;
	
	return 1 + getsum (x-1, y) + getsum (x+1, y) + getsum (x, y-1) + getsum (x, y+1);
}

bool check () {
	memset (used, 0, sizeof used);
	for (int i = 0;i  n*m) return ;
	if (sum == K) {
		if (check ()) ans ++;
		return ;
	}
	
	for (int i = x;i