侧边栏壁纸
博主头像
GabrielxD

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

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-05-18 / 0 评论 / 0 点赞 / 52 阅读 / 720 字 / 正在检测是否收录...

题目

核桃的数量


如图所示,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

评论区