小华最多能得到多少克黄金 - 华为OD统一考试(D卷)
OD统一考试（D卷）
分值： 100分
题解： Java / Python / C++
题目描述
小华按照地图去寻宝，地图上被划分成 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
输出描述
最多能获得多少克黄金
示例1
输入：
40 40 18
输出：
1484
说明：
示例2
输入：
4 5 7
输出：
20
说明：
如图每个单元格中的数位之和不大于
7
7，都是符合要求的，所以可以最多可获得
20
20 克黄金
题解
这道题目是一个搜索问题，需要从入口
(0, 0)开始，使用深度优先搜索（DFS）来遍历满足数位之和条件的方格。在搜索的过程中，需要判断坐标的有效性和数位之和是否满足条件。同时，使用一个二维数组vis来记录已经访问过的方格，避免重复访问。具体步骤如下：
- 定义一个函数
sum_of_digits用于计算一个数字的数位之和。- 定义 DFS 函数，接收当前坐标
(r, c)，在函数中进行如下判断：
- 验证坐标有效性：
r和c不越界，且当前方格未被访问。- 计算数位之和，如果数位之和大于
k，则不再递归下去。- 在 DFS 函数中标记当前方格为已访问，并增加黄金数量。
- 递归调用 DFS 函数，分别向上、向下、向左、向右四个方向进行搜索。
- 主函数中读入
m、n、k的值，初始化gold为 0，并创建一个二维数组vis用于记录访问状态。- 调用 DFS 函数开始搜索，从入口
(0, 0)开始。- 输出最终的黄金数量。
复杂度分析
时间复杂度：在最坏情况下，每个方格可能都需要访问一次，因此时间复杂度为 O(m * n)。
空间复杂度：使用了一个二维数组
vis来记录访问状态，因此空间复杂度为 O(m * n)。同时，递归调用的栈空间也需要考虑，但在这里由于递归深度不会很大，可以近似为 O(1)。
Java
import java.util.Scanner;
/**
* @author code5bug
*/
public class Main {
static int gold;
static int m, n, k;
static boolean[][] vis;
// 求数位之和
static int sumOfDigits(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
static void dfs(int r, int c) {
// 验证坐标有效性
if (r < 0 || c < 0 || r >= m || c >= n || vis[r][c]) return;
// 求数位之和，如果数位之和大于 k，则不再递归下去了
if (sumOfDigits(r) + sumOfDigits(c) > k) return;
vis[r][c] = true;
gold++;
// 递归调用
dfs(r - 1, c);
dfs(r + 1, c);
dfs(r, c - 1);
dfs(r, c + 1);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
m = scanner.nextInt();
n = scanner.nextInt();
k = scanner.nextInt();
// 初始化
gold = 0;
vis = new boolean[m][n];
dfs(0, 0);
System.out.println(gold);
}
}
Python
def sum_of_digits(num):
# 求数位之和
return sum([int(c) for c in str(num)])
def dfs(r, c):
global gold, m, n, k, vis
# 验证坐标有效性
if r < 0 or c < 0 or r >= m or c >= n or vis[r][c]:
return
# 求数位之和，如果数位之和大于 k，则不再递归下去了
if sum_of_digits(r) + sum_of_digits(c) > k:
return
vis[r][c] = True
gold += 1
# 递归调用
dfs(r - 1, c)
dfs(r + 1, c)
dfs(r, c - 1)
dfs(r, c + 1)
# 主函数
m, n, k = map(int, input().split())
# 初始化
gold = 0
vis = [[False] * n for _ in range(m)]
dfs(0, 0)
print(gold)
C++
#include <bits/stdc++.h>
using namespace std;
int gold;
int m, n, k;
bool vis[55][55];
// 求数位之和
int sum_of_digits(int num)
{
int sum = 0;
while (num) {
sum += num % 10;
num /= 10;
}
return sum;
}
void dfs(int r, int c)
{
// 验证坐标有效性
if (r < 0 || c < 0 || r >= m || c >= n || vis[r][c]) return;
// 求数位之和，如果数位之和大于k，则不再递归下去了
if (sum_of_digits(r) + sum_of_digits(c) > k) return;
vis[r][c] = true;
gold++;
// 递归调用
dfs(r - 1, c);
dfs(r + 1, c);
dfs(r, c - 1);
dfs(r, c + 1);
}
int main()
{
cin >> m >> n >> k;
// 初始化
gold = 0;
memset(vis, 0, sizeof(vis));
dfs(0, 0);
cout << gold << endl;
return 0;
}
相关练习题
#面经##华为od##华为od题库##秋招##校招#整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏
