当前位置：首页 > article >正文

[蓝桥杯]剪格子

article 2025/9/17 0:47:09

剪格子

题目描述

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

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

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

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

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

输入描述

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

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

输出描述

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

输入输出样例

示例

输入

输出

运行限制

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

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

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

方法思路

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

检查总和：计算网格所有元素的总和。如果总和为奇数，则无法分割，输出0。
深度优先搜索：从左上角格子开始DFS，探索所有四连通区域：
- 剪枝优化：若当前区域和超过总和一半或格子数已超过最小解，则回溯。
- 解验证：当区域和等于总和一半时，检查剩余部分是否连通（使用BFS）。
连通性检查：对剩余部分进行BFS，验证其连通性。

结果输出：记录满足条件的最小格子数，若未找到解则输出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;
}

代码解释

输入处理：
- 读取网格的行数 n 和列数 m。
- 使用二维向量 grid 存储网格元素，visited 标记访问状态。
- 计算网格元素总和 total。
总和检查：
- 若总和为奇数，直接输出 0 并结束（无法分割）。
深度优先搜索：
- 从左上角 (0,0) 开始DFS，标记该格子已访问。
- 剪枝：当前区域和超过 total/2 或格子数超过最小解时回溯。
- 解验证：当区域和等于 total/2 时，调用 check_connectivity 检查剩余部分连通性。
连通性检查：
- 使用BFS遍历剩余格子：
  - 统计剩余格子数量 remain_count。
  - 从第一个剩余格子开始BFS，统计连通格子数 cnt。
  - 若 cnt == remain_count 则剩余部分连通。
结果输出：
- 若找到解，输出最小格子数 min_count。
- 若未找到解，输出 0。