如下图, 有12张连在一起的12生肖的邮票。现在你要从中剪下5张来，要求必须是连着的。（仅仅连接一个角不算相连）
比如，下面两张图中，粉红色所示部分就是合格的剪取
请你计算，一共有多少种不同的剪取方法。
输出
请填写表示方案数目的整数。
方案：dfs遍历所有方案，判断是否合法
#include <iostream>
#include <cstring>using namespace std;const int N = 15;int res;
int g[N][N];
int a[12] = {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1};
//判断图的联通性
void dfs(int i, int j){g[i][j] = 0;if (i - 1 >= 0 && i - 1 < 3 && g[i - 1][j] == 1) dfs(i - 1, j);if (i + 1 >= 0 && i + 1 < 3 && g[i + 1][j] == 1) dfs(i + 1, j);if (j - 1 >= 0 && j - 1 < 4 && g[i][j - 1] == 1) dfs(i, j - 1);if (j + 1 >= 0 && j + 1 < 4 && g[i][j + 1] == 1) dfs(i, j + 1);}
bool check(){for (int i = 0; i < 3; i ++ )for (int j = 0; j < 4; j ++ )if (a[i * 4 + j] == 1) g[i][j] = 1;else g[i][j] = 0;int cnt = 0;for (int i = 0; i < 3; i ++ )for (int j = 0; j < 4; j ++ )if (g[i][j] == 1){dfs(i, j);cnt ++;}return cnt == 1;
}void df(int u){if (u == 12){if (check()) res ++;return;}for (int i = u; i < 12; i ++ ){swap(a[i], a[u]);df(u + 1);swap(a[i], a[u]);}
}int main(){df(0);cout << res << endl;return 0;
}
结果
70156800
106690ms
