侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-05-18 / 0 评论 / 0 点赞 / 223 阅读 / 718 字
温馨提示:
本文最后更新于 2023-04-15,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

剪格子


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

image-20220518214205251

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

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

image-20220518214250942

输入:

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

输出:

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

示例 1:

image-20220518214205251
用户输入:
3 3
10 1 52
20 30 1
1 2 3
程序输出:
3

示例 2:

image-20220518214250942
用户输入:
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; // 回溯
	}
}
0

评论区