华为OD机试 - 地图寻宝 - 深度优先搜索BFS（Java 2024 D卷 200分）

在这里插入图片描述

华为OD机试 2024D卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（D卷+C卷+A卷+B卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

小华按照地图去寻宝，地图上被划分成 n nn 行和 m mm 列的方格，横纵坐标范围分别是 [ 0 , n − 1 ] [0, n-1][0,n−1] 和 [ 0 , m − 1 ] [0, m-1][0,m−1]。

在横坐标和纵坐标的数位之和不大于 k kk 的方格中存在黄金（每个方格中仅存在一克黄金），但横坐标和纵坐标数位之和大于 k kk 的方格存在危险不可进入。小华从入口 ( 0 , 0 ) (0,0)(0,0) 进入，任何时候只能向左，右，上，下四个方向移动一格。

请问小华最多能获得多少克黄金？

二、输入描述

坐标取值范围如下：

0 ≤ m ≤ 5 0 ≤ m ≤ 50≤m≤5

0 ≤ n ≤ 5 0 ≤ n ≤ 50≤n≤5

k kk 的取值范围如下：0 ≤ k ≤ 10 0 ≤ k ≤ 100≤k≤10

输入中包含 3 个字数，分别是 m, n, k

三、输出描述

输出小华最多能获得多少克黄金。

1、输入

40 40 18

2、输出

1484

3、说明

四、解题思路

这个问题可以看作是一个典型的搜索问题，我们需要在一个二维矩阵中进行深度优先搜索（DFS）或者广度优先搜索（BFS），来计算在满足条件的方格中最多能获得的黄金数量。

解题步骤：

坐标数位和计算：
- 定义一个辅助函数来计算一个数的各位数之和。
深度优先搜索（DFS）：
- 使用递归的方式进行DFS，从起点 (0, 0) 开始，向四个方向（上、下、左、右）移动。
- 在每次移动之前，检查新的位置是否已经访问过，以及该位置的数位之和是否小于等于 k。
- 如果满足条件，则继续递归搜索，并累计黄金数量。
状态记录：
- 使用一个二维数组 visited 来记录已经访问过的位置，防止重复访问。

五、Java算法源码

public class Test01 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入的m, n, k
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        scanner.close();

        // 初始化访问记录数组
        boolean[][] visited = new boolean[m][n];

        // 通过DFS计算最大可获得黄金数量
        int result = dfs(0, 0, m, n, k, visited);

        // 输出结果
        System.out.println(result);
    }

    // 计算数位之和的辅助函数
    private static int digitSum(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }

    // 深度优先搜索函数
    private static int dfs(int x, int y, int m, int n, int k, boolean[][] visited) {
        // 检查边界条件和数位之和条件
        if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y] || (digitSum(x) + digitSum(y) > k)) {
            return 0;
        }

        // 标记当前位置为已访问
        visited[x][y] = true;

        // 当前格子有1克黄金
        int gold = 1;

        // 向四个方向递归搜索
        gold += dfs(x + 1, y, m, n, k, visited);
        gold += dfs(x - 1, y, m, n, k, visited);
        gold += dfs(x, y + 1, m, n, k, visited);
        gold += dfs(x, y - 1, m, n, k, visited);

        return gold;
    }
}