华为OD机试统一考试 - 小华地图寻宝

题目描述

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

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

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

输入描述

坐标取值范围如下：

• 0 ≤ m ≤ 50
• 0 ≤ n ≤ 50

k 的取值范围如下：

• 0 ≤ k ≤ 100

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

输出描述

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

用例

题目解析

本题题目描述有些歧义

在横坐标和纵坐标的数位之和不大于 k 的方格中存在黄金（每个方格中仅存在一克黄金）

和

但横坐标和纵坐标之和大于 k 的方格存在危险不可进入

这两句话有点矛盾，所谓横坐标和纵坐标的数位之和，比如：

• 横坐标是10，那么横坐标的数位和 = 1 + 0 = 1
• 纵坐标是21，那么纵坐标的数位和 = 2 + 1 = 3
• 横坐标和纵坐标的数位之和 = 1 + 3 = 4

但是横坐标和纵坐标之和

• 横坐标是10，纵坐标是21，横坐标和纵坐标之和 = 10 + 21 = 31

和考友确认后，上面“横坐标和纵坐标之和”其实也是数位之和，即

横坐标和纵坐标数位之和大于 k 的方格存在危险不可进入

因此，本题其实就是图的遍历问题，可以使用深度优先搜索DFS，或者广度优先搜索BFS处理。

从（0，0）点开始，然后进行深搜或者广搜，其上下左右四个新位置，新位置是否可以进入的条件是：

• 新位置不越界
• 新位置未被访问过
• 新位置的横坐标、纵坐标的数位之和 <= k

每进入一个位置，则获得黄金1克。

import Foundation

class DFSCalss {
    // 该方法用于求解 0 ~ maxSize - 1 各个数对应的数位和，提前计算好，避免后期重复计算某个数的数位和// 数位和数组
    var digitSums: [Int] = []

    // 横坐标最大值
    var m = 0
    // 纵坐标最大值
    var n = 0
    // 方格中存在黄金的数位之和k临界区
    var k = 0
    // 记录题解
    var ans = 0
    // 记录已访问过的位置，避免重复统计
    var visited: [Int] = []
    // 上下左右偏移量
    let offsets = [
        [-1, 0],
        [1, 0],
        [0, -1],
        [0, 1],
    ]

    func digitSum(_ maxSize: Int) {
        digitSums = Array(repeating: 0, count: maxSize + 1)
        for i in 0 ... maxSize {
            var temp = i
            while temp > 0 {
                digitSums[i] += temp % 10
                temp = temp / 10
            }
        }
    }

    // 深度优先搜索遍历矩阵
    func dfs(_ x: Int, _ y: Int) {
        // 如果对应位置越界，或者已访问过，或者横坐标、纵坐标的数位和之和超过了k，则不能进入
        if x < 0
            || x >= m
            || y < 0
            || y >= n
            || visited.contains(x * n + y)
            || digitSums[x] + digitSums[y] > k { return }

        // 否则可以进入，且获得黄金
        visited.append(x * n + y)
        ans += 1

        // 继续遍历上、下、左、右方向上的新位置继续深搜
        for offset in offsets {
            let newX = x + offset[0]
            let newY = y + offset[1]
            dfs(newX, newY)
        }
    }
}

func ODTest_10() {
    print("输入描述,坐标取值范围，用空格隔开")
    let locations = readLine()?.split(separator: " ").map { Int($0) ?? 0 } ?? []
    let dfs = DFSCalss()
    dfs.m = locations[0]
    dfs.n = locations[1]
    dfs.k = locations[2]
    dfs.digitSum(max(dfs.m, dfs.n))
    dfs.dfs(0, 0)
    print("输出小华最多能获得多少克黄金")
    print("\(dfs.ans)")
}