剪邮票

如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。

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

请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

 

 

 

 

 

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 using namespace std;
 6 const int row = 3;
 7 const int col = 4;
 8 bool vis[row][col];
 9 int map[row][col];
10 int dir[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
11 int ans;
12 void dfs(int x, int y)
13     {
14         vis[x][y] = true;
15         for(int i = 0; i < 4; ++i){
16             int nx = x + dir[i][0];
17             int ny = y + dir[i][1];
18             if(nx<0||nx>=row || ny<0||ny>=col) continue;
19             if(vis[nx][ny] || !map[nx][ny]) continue;
20             //vis[nx][ny] = true;
21             dfs(nx,ny);
22         }
23     }
24 int main()
25     {
26         int b[] = {0,0,0,0,0,0,0,1,1,1,1,1};
27         do{
28             memset(vis,false,sizeof(vis));
29             memset(map,0,sizeof(map));
30             int cnt = 0;
31             for(int i = 0; i < row; ++i){
32                 for(int j = 0; j < col; ++j){
33                     map[i][j] = b[cnt++];
34                 }
35             }
36             int num = 0;
37             for(int i = 0; i < row; ++i){//这里就是判断连通分量个数 如果这5值为1的点为一个连通分量 则 满足条件
38                 for(int j = 0; j < col; ++j){
39                     if(!vis[i][j] && map[i][j]){
40                         ++num;
41                     //    vis[i][j] = true;
42                         dfs(i,j);
43                     }
44                 }
45             }
46             if(num == 1)//连通分量数为1 即5个位置连通
47                 ++ans;
48             
49         }while(next_permutation(b,b+12));
50         
51         cout <<ans;
52         return 0;
53     }