[蓝桥杯]剪格子

剪格子

题目描述

如下图所示，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;
       }
   
       // 从左上角开始DFS
       visited[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（输出结果）。