剪格子
剪格子
如下图所示，$3 \times 3$ 的格子中填写了一些整数。
我们沿着图中的红色线剪开，得到两个部分，每个部分的数字和都是 $60$。
本题的要求就是请你编程判定：对给定的 $m \times n$ 的格子中的整数，是否可以分割为两个连通的部分，使得这两个区域的数字和相等。
如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。
如果无法分割，则输出 $0$。
输入格式
第一行包含两个整数 $m,n$ ,表示表格的宽度和高度。
接下来是 $n$ 行，每行 $m$ 个正整数，用空格分开。
输出格式
在所有解中，包含左上角的分割区可能包含的最小的格子数目。
如果无法分割，则输出 $0$。
数据范围
$1 \leq n,m < 10$,
格子内的数均在 $1$ 到 $10000$ 之间。
输入样例1：
3 3 10 1 52 20 30 1 1 2 3
输出样例1：
3
输入样例2：
4 3 1 1 1 1 1 30 80 2 1 1 1 100
输出样例2：
10
解题思路
这道题很容易想到深搜，但也有几个难点。
首先要保证剪掉格子后，只有两个连通块。
比如下图，如果剪掉的是红色区域的格子，那么最后会得到三个连通块。
判断是否只有两个连通块的方法需要用到并查集。我们会把剪掉的格子放入一个集合中，然后用总格子的数量减去这个集合元素的数量，那么就会得到剩余未被剪掉格子的数量，同时一开始这些未被剪掉的格子各种都是一个独立的连通块，数量就是未被剪掉格子的数量。我们就是去看看能否把这些格子都并成一个连通块。
然后遍历每一个格子，如果这个格子不属于这个集合的元素（意味着这个格子未被剪掉），那么就检查这个格子的四个方向的相邻格子，如果相邻的格子未被剪掉，并且这在并查集中的根节点不同（两个格子还没并在一起），那么就把其中一个根节点并到另一个根节点，同时连通块数量减$1$。最后，如果这些未被剪掉格子所得的连通块数量为$1$，说明这些未被剪掉格子是连通的，否则就不连通。
另外一个问题是，我们剪的格子也是要满足连通的。我们一般的搜索顺序是从上一个搜到的格子往四个方向继续搜，但这样会有一个问题，就是搜到的格子都是一笔画的，也就是说这种搜索方式搜出来的是一条路径而不是一个连通块。
上面的图就是这种搜索方式的结果，如果是下面这种图，这种搜索方式是搜不出来的：
可以发现对于这种情况，无论是一笔还是两笔都是无法画完的，需要画多笔。
因此我们应该从左上角开始搜，在搜索的时候维护一个集合，就是上面提到的集合，这个集合存放已剪且连通的格子。我们每次搜索的时候不是从上一个搜到的格子搜，而是从这个集合的每一个格子搜，这样才可以搜到满足多笔的情况。
枚举集合中的每一个格子，然后对于每一个格子都往四个方向扩展，判断相邻的格子能否往下搜，如果可以的话，就将这个格子加入集合中，继续往下搜；回溯的时候把这格子从集合删除，继续遍历集合中的其他格子。
这里还需要剪支。就是对于某个已经剪过的连通块，那么之前一定是已经搜过这种情况的了，我们就没必要再对这种情况搜一次了，因此我们开一个哈希表来记录每次搜索过的情况，对于同一个情况应该得到同一个结果，不同的情况得到不同的结果。因为每一个情况都是一个二维矩阵，因此我们需要状态压缩，方法是字符串哈希，把每种情况当作一个字符串来处理。因为集合中的点都是乱序的，为了保证一致性，我们先对集合中的格子进行排序，然后把每个格子的坐标组成一个字符串，进行哈希。
最后AC代码如下：
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 typedef unsigned long long ULL; 8 typedef pair<int, int> PII; 9 10 const int N = 20, P = 131; 11 12 int n, m, ans = N * N; 13 int graph[N][N]; 14 bool vis[N][N]; 15 int sum; 16 int fa[N * N]; 17 PII a[N * N]; 18 unordered_set st; 19 int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; 20 21 int find(int x) { 22 return fa[x] == x ? fa[x] : fa[x] = find(fa[x]); 23 } 24 25 bool is_connect(int cnt) { // 判断剩余部分是否是一个连通块 26 for (int i = 0; i < n * m; i++) { 27 fa[i] = i; 28 } 29 30 int num = n * m - cnt; // 一开始每一个未被剪得格子都是单独的一个连通块 31 32 // 遍历每一个格子 33 for (int i = 0; i < n; i++) { 34 for (int j = 0; j < m; j++) { 35 if (!vis[i][j]) { // 格子未被剪掉 36 for (int k = 0; k < 4; k++) { // 往四个方向扩展 37 int x = i + dx[k], y = j + dy[k]; 38 if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y]) { 39 int p1 = find(x * m + y), p2 = find(i * m + j); // 求这两个格子所在并查集的父节点 40 if (p1 != p2) { // 这两个格子还不再同一个并查集中 41 fa[p1] = p2; // 把这两个合并，意味着这两个格子在同一个连通块 42 num--; // 连通块数量减1 43 } 44 } 45 } 46 } 47 } 48 } 49 50 return num == 1; // 最后判断连通块数量是否只有一个 51 } 52 53 bool is_exist(int cnt) { // 判断某种情况是否已经搜过 54 PII tmp[N * N]; 55 memcpy(tmp, a, sizeof(a)); // 因为要排序，会改变原集合中元素的顺序，因此进行备份 56 57 sort(tmp, tmp + cnt); 58 59 ULL key = 0; // 这种情况的哈希值 60 for (int i = 0; i < cnt; i++) { 61 key = key * P + tmp[i].first + 1; // 哈希不能有0，因为一个0和两个0得到的结果是一样的 62 key = key * P + tmp[i].second + 1; 63 } 64 65 if (st.count(key)) return true; // 如果这种情况出现过返回true 66 st.insert(key); // 否则这种情况未出现过，把这种情况加入哈希表中，返回false 67 return false; 68 } 69 70 void dfs(int cnt, int s) { 71 if (s > sum - s || cnt >= ans || !is_connect(cnt)) return; // 剪支 72 if (s == sum - s) { 73 ans = cnt; 74 return; 75 } 76 77 // 遍历集合中的每一个格子 78 for (int i = 0; i < cnt; i++) { 79 int x = a[i].first, y = a[i].second; 80 for (int j = 0; j < 4; j++) { 81 int xx = x + dx[j], yy = y + dy[j]; 82 if (xx >= 0 && xx < n && yy >= 0 && yy < m && !vis[xx][yy]) { 83 a[cnt] = {xx, yy}; 84 if (is_exist(cnt + 1)) continue; // 已经搜过的情况就不再搜了 85 86 vis[xx][yy] = true; 87 dfs(cnt + 1, s + graph[xx][yy]); 88 vis[xx][yy] = false; 89 } 90 } 91 } 92 } 93 94 int main() { 95 scanf("%d %d", &m, &n); 96 for (int i = 0; i < n; i++) { 97 for (int j = 0; j < m; j++) { 98 scanf("%d", &graph[i][j]); 99 sum += graph[i][j]; 100 } 101 } 102 103 if (sum % 2 == 0) { 104 vis[0][0] = true; 105 a[0] = {0, 0}; 106 dfs(1, graph[0][0]); 107 } 108 109 printf("%d", ans == N * N ? 0 : ans); 110 111 return 0; 112 }
参考资料
AcWing 1206. 剪格子（蓝桥杯C++ AB组辅导课）：https://www.acwing.com/video/802/