[蓝桥杯]剪格子

剪格子

题目描述

如下图所示，3 x 3 的格子中填写了一些整数。

我们沿着图中的红色线剪开，得到两个部分，每个部分的数字和都是 60。

本题的要求就是请你编程判定：对给定的 m×nm×n 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。

如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。

如果无法分割，则输出 0。

输入描述

输入描述

程序先读入两个整数 m,nm,n 用空格分割 (m,n<10)(m,n<10)，表示表格的宽度和高度。

接下来是 nn 行，每行 mm 个正整数，用空格分开。每个整数不大于 104104。

输出描述

在所有解中，包含左上角的分割区可能包含的最小的格子数目。

输入输出样例

示例

输入

3 3
10 1 52
20 30 1
1 2 3

输出

3

运行限制

• 最大运行时间：5s
• 最大运行内存: 64M

总通过次数: 2669  |  总提交次数: 3114  |  通过率: 85.7%

难度: 中等   标签: 2013, 省赛, 搜索

方法思路

题目要求将网格分割成两个连通区域，使得两个区域的数字和相等，并输出包含左上角格子的最小格子数目。解决思路如下：

1. 检查总和：计算网格所有元素的总和。如果总和为奇数，则无法分割，输出0。

2. 深度优先搜索：从左上角格子开始DFS，探索所有四连通区域：

   • 剪枝优化：若当前区域和超过总和一半或格子数已超过最小解，则回溯。

   • 解验证：当区域和等于总和一半时，检查剩余部分是否连通（使用BFS）。

3. 连通性检查：对剩余部分进行BFS，验证其连通性。

4. 结果输出：记录满足条件的最小格子数，若未找到解则输出0。

   #include <iostream>
   #include <vector>
   #include <queue>
   #include <climits>
   using namespace std;int m, n;
   vector<vector<int>> grid;
   vector<vector<bool>> visited;
   int total = 0;
   int min_count = INT_MAX;// 方向数组：上、右、下、左
   int dx[4] = {-1, 0, 1, 0};
   int dy[4] = {0, 1, 0, -1};// 检查剩余部分连通性
   bool check_connectivity(int count) {int total_count = n * m;int remain_count = total_count - count;if (remain_count == 0) return true;// 找到第一个剩余格子int start_i = -1, start_j = -1;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (!visited[i][j]) {start_i = i;start_j = j;break;}}if (start_i != -1) break;}// BFS遍历剩余格子vector<vector<bool>> temp_vis(n, vector<bool>(m, false));queue<pair<int, int>> q;q.push({start_i, start_j});temp_vis[start_i][start_j] = true;int cnt = 1;while (!q.empty()) {auto [x, y] = q.front();q.pop();for (int k = 0; k < 4; k++) {int nx = x + dx[k];int ny = y + dy[k];if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && !temp_vis[nx][ny]) {temp_vis[nx][ny] = true;cnt++;q.push({nx, ny});}}}return cnt == remain_count;
   }// 深度优先搜索
   void dfs(int i, int j, int sum, int count) {// 剪枝：超过总和一半或已找到更优解if (sum > total / 2) return;if (count >= min_count) return;// 找到可行解并检查剩余部分连通性if (sum == total / 2) {if (check_connectivity(count)) {min_count = min(min_count, count);}return;}// 四方向扩展for (int k = 0; k < 4; k++) {int ni = i + dx[k];int nj = j + dy[k];if (ni >= 0 && ni < n && nj >= 0 && nj < m && !visited[ni][nj]) {visited[ni][nj] = true;dfs(ni, nj, sum + grid[ni][nj], count + 1);visited[ni][nj] = false;}}
   }int main() {cin >> m >> n;grid.resize(n, vector<int>(m));visited.resize(n, vector<bool>(m, false));// 读入网格并计算总和for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];total += grid[i][j];}}// 总和为奇数则无解if (total % 2 != 0) {cout << 0 << endl;return 0;}// 从左上角开始DFSvisited[0][0] = true;dfs(0, 0, grid[0][0], 1);// 输出结果if (min_count == INT_MAX) {cout << 0 << endl;} else {cout << min_count << endl;}return 0;
   }

   代码解释

5. 输入处理：

   • 读取网格的行数 n 和列数 m。

   • 使用二维向量 grid 存储网格元素，visited 标记访问状态。

   • 计算网格元素总和 total。

6. 总和检查：

   • 若总和为奇数，直接输出 0 并结束（无法分割）。

7. 深度优先搜索：

   • 从左上角 (0,0) 开始DFS，标记该格子已访问。

   • 剪枝：当前区域和超过 total/2 或格子数超过最小解时回溯。

   • 解验证：当区域和等于 total/2 时，调用 check_connectivity 检查剩余部分连通性。

8. 连通性检查：

   • 使用BFS遍历剩余格子：

     • 统计剩余格子数量 remain_count。

     • 从第一个剩余格子开始BFS，统计连通格子数 cnt。

     • 若 cnt == remain_count 则剩余部分连通。

9. 结果输出：

   • 若找到解，输出最小格子数 min_count。

   • 若未找到解，输出 0。

示例说明

对于输入样例：

3 3
10 1 52
20 30 1
1 2 3

1. 总和：120（total/2 = 60）。

2. 可行解：格子 (0,0)=10、(1,0)=20、(1,1)=30（和=60）。

3. 剩余部分：其他格子连通（通过BFS验证）。

4. 最小格子数：3（输出结果）。