【DFS, 回溯】剪格子【蓝桥杯】

题目

剪格子

---

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

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

本题的要求就是请你编程判定：对给定的 m x n 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。
如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。
如果无法分割，则输出 0。

输入：

• 程序先读入两个整数 m n 用空格分割 (m,n<10) 表示表格的宽度和高度。
• 接下来是 n 行，每行 m 个正整数用空格分开，每个整数不大于 10000。

输出：

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

示例 1：

用户输入：
3 3
10 1 52
20 30 1
1 2 3
程序输出：
3

示例 2：

用户输入：
4 3
1 1 1 1
1 30 80 2
1 1 1 100
程序输出：
10

资源限制

• 峰值内存消耗 < 64M
• CPU消耗 < 5000ms

解题

方法一：DFS 剪枝 回溯

思路

从左上角开始连接所有可能的格子（只能向上下左右连接，不能斜向），如果当前连接的所有格子加起来和(sum)为所有格子总和(total)的一半，则当前经过的路径长度(step)是一个有效解，维护一个最小的有效解(ans)。

使用深搜实现以上的步骤，其中：

• 如果当前要连接的格子超出边界或者已经被访问过了(isVisited)，就直接结束这条递归路线。
• 如果 sum > total / 2 就需要进行剪枝。
• 每连接一个格子在进行更深的选择递归之前把该格子标记为已访问，所有可能性递归完之后进行回溯，再把该格子标未访问。

代码

public class Main {
	static int colLen, rowLen, total;
	static int[][] grids;
	static boolean[][] isVisited;
	static int ans = Integer.MAX_VALUE;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		colLen = sc.nextInt();
		rowLen = sc.nextInt();
		grids = new int[rowLen][colLen];
		isVisited = new boolean[rowLen][colLen];
		for (int[] row : grids) {
			for (int i = 0; i < colLen; i++) {
				total += (row[i] = sc.nextInt());
			}
		}
		sc.close();
		
		dfs(0, 0, 0, 0);
		System.out.println(ans);
	}
	
	static void dfs(int row, int col, int step, int sum) {
		if (row < 0 || row >= rowLen || col < 0 || col >= colLen || isVisited[row][col]) return;
		
		sum += grids[row][col];
		step++;
		if (sum == total / 2) {
			ans = Math.min(ans, step);
			return;
		}
		if (sum > total / 2) return;
		isVisited[row][col] = true;
		dfs(row - 1, col, step, sum); // 向上
		dfs(row + 1, col, step, sum); // 向下
		dfs(row, col - 1, step, sum); // 向左
		dfs(row, col + 1, step, sum); // 向右
		isVisited[row][col] = false; // 回溯
	}
}