华为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
    // 方格中存在黄金的