[蓝桥杯2016初赛]剪邮票【全排列，连通块】
题目描述
如下图, 有12张连在一起的12生肖的邮票。现在你要从中剪下5张来，要求必须是连着的。（仅仅连接一个角不算相连）
比如，下面两张图中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。
这个题是个填空题， 我想许多人可能和我一样，会用深度优先搜索做。但是像这种枚举每一个点，来索索，得出的结果是错的，因为其中有重复的元素。而且这样取出来的邮票一般是L型；
接下来介绍，全排列加dfs求连通块。
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 int a[] = {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1}; 7 int g[3][4]; 8 int ans = 0; 9 void dfs(int x, int y){//求连通块 10 11 g[x][y] = 0; 12 13 for(int i = -1; i <= 1; ++ i){ 14 for(int j = -1; j <= 1; ++ j){ 15 if(abs(i) == abs(j))continue; 16 int dx = x + i; 17 int dy = y + j; 18 19 if(dx >= 0 && dx < 3 && dy >= 0 && dy < 4 && g[dx][dy] == 1){ 20 21 dfs(dx, dy); 22 } 23 24 } 25 } 26 27 } 28 void f(){ 29 30 memset(g, 0, sizeof(g)); 31 for(int i = 0; i < 12; ++ i){ 32 if(a[i] == 1) 33 g[i / 4][i % 4] = 1;//一维转二维 34 } 35 bool flag = false; 36 for(int i = 0; i < 3; ++ i){ 37 for(int j = 0; j < 4; ++ j){ 38 if(g[i][j] == 1){ 39 if(!flag) 40 dfs(i, j), flag = true; 41 else 42 return; 43 } 44 } 45 } 46 ans ++; 47 } 48 49 50 int main(){ 51 52 do{//枚举全排列 53 f(); 54 55 }while(next_permutation(a, a + 12)); 56 cout << ans << endl; 57 return 0; 58 }