蓝桥杯剪邮票

思路：dfs每个格子选或不选，选定5个格子后判连通。这样写好像不会漏情况。结果是116
 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 int map[3][4];
 5 int temp_map[3][4];
 6 bool in[3][4];
 7 int dx[4] = {0,1,0,-1};
 8 int dy[4] = {1,0,-1,0}; 
 9 void dfs_connected(int x,int y)
10 {
11     temp_map[x][y] = false;
12     for(int k = 0;k < 4;k ++)
13     {
14         int nx = x + dx[k];
15         int ny = y + dy[k];
16         if(nx >= 0 && nx < 3 && ny >= 0 && ny < 4 && temp_map[nx][ny])
17         {
18             dfs_connected(nx,ny);
19         }
20     }
21 }
22 int dfs(int x,int y,int cur)
23 {
24     if(x == 3)
25         return 0;
26     if(cur == 5)
27     {
28         for(int i = 0;i < 3;i ++)
29         {
30             for(int j = 0;j < 4;j ++)
31             {
32                 temp_map[i][j] = in[i][j];
33             }
34         }
35         int cnt = 0;
36         for(int i = 0;i < 3;i ++)
37         {
38             for(int j = 0;j < 4;j ++)
39             {
40                 if(temp_map[i][j])
41                 {
42                    dfs_connected(i,j);
43                    cnt ++;    
44                 } 
45             }
46         }
47         if(cnt > 1)
48             return 0;
49         return 1;
50     } 
51     int nx;
52     int ny;
53     int cnt = 0;
54     if(y < 3)
55     {
56         ny = y + 1;
57         nx = x; 
58     }
59     else
60     {
61         ny = 0;
62         nx = x + 1;
63     }
64     if(x == -1 && y == 0)
65     {
66         nx = ny = 0;
67     }
68     in[nx][ny] = true;
69     cnt += dfs(nx,ny,cur + 1);
70     in[nx][ny] = false;
71     cnt += dfs(nx,ny,cur);
72     return cnt;
73 }
74 int main()
75 {
76     cout << dfs(-1,0,0) << endl;
77     return 0;    
78 }
蓝桥杯 剪邮票

蓝桥杯剪邮票
