题目描述与示例
题目描述
小华按照地图去寻宝，地图上被划分成
n
n
n 行和
m
m
m 列的方格，横纵坐标范围分别是
[
0
,
n
−
1
]
[0, n-1]
[0,n−1] 和
[
0
,
m
−
1
]
[0, m-1]
[0,m−1]。
在横坐标和纵坐标的数位之和不大于
k
k
k 的方格中存在黄金（每个方格中仅存在一克黄金），但横坐标和纵坐标数位之和大于
k
k
k 的方格存在危险不可进入。小华从入口
(
0
,
0
)
(0,0)
(0,0) 进入，任何时候只能向左，右，上，下四个方向移动一格。
请问小华最多能获得多少克黄金？
输入描述
坐标取值范围如下：
0
≤
m
≤
5
0 ≤ m ≤ 5
0≤m≤5
0
≤
n
≤
5
0 ≤ n ≤ 5
0≤n≤5
k
k
k 的取值范围如下：
0
≤
k
≤
10
0 ≤ k ≤ 10
0≤k≤10
输入中包含 3 个字数，分别是 m, n, k
输出描述
输出小华最多能获得多少克黄金
示例一
输入
40 40 18
输出
1484
示例二
输入
5 4 7
输出
20
解题思路
计算数位和
本题的重点在于理解数位和的概念。
所谓数位和，指的是一个正整数的各个位的和。比如11的数位和是1+1 = 2
对于任意一个正整数n，其数位和可以通过以下两种方式任选其一进行计算。在效率上，数学方法略优于字符串方法，但因为数据量不大，所以都可以使用。
数学方法
def cal_digit_sum(n):
ans = 0
while n != 0:
ans += n % 10
n //= 10
return ans
字符串方法
def cal_digit_sum(n):
return sum(int(i) for i in str(n))
构建数位和矩阵
在拿到地图的大小n*m之后，就可以通过双重循环遍历的方式，构建出每一个位置的数位和矩阵grid。
grid = [[0] * m for _ in range(n)]
for i in range(n):
for j in range(m):
grid[i][j] = cal_digit_sum(i) + cal_digit_sum(j)
从起点开始进行搜索
拿到数位和矩阵grid之后，由于小华从起点出发上下左右均可以移动，所以问题就转化为了从起点(0, 0)开始进行图的索能够到达多大面积的地图。
这个问题用DFS或者BFS都可以完成。直接套模板即可。
代码
解法一：DFS
python
# 题目：【DFS/BFS】2023C-地图寻宝
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：DFS
# 代码看不懂的地方，请直接在群上提问
import sys
# 地图最大范围为50*50 = 2500，超过了最大递归深度的默认值1000
# 设置最大递归深度
sys.setrecursionlimit(100000)
# 表示四个方向的数组
DIRECTIONS = [(0,1), (1,0), (-1,0), (0,-1)]
# 构建非负整数n的数位和的函数
def cal_digit_sum(n):
ans = 0
while n != 0:
ans += n % 10
n //= 10
return ans
def dfs(i, j, m, n, k, checklist, grid):
global ans
checklist[i][j] = 1
ans += 1
for di, dj in DIRECTIONS:
ni, nj = i+di, j+dj
# 注意此处的判断条件为grid[ni][nj] <= k
if 0 <= ni < m and 0 <= nj < n and checklist[ni][nj] == 0 and grid[ni][nj] <= k:
dfs(ni, nj, m, n, k, checklist, grid)
# 输入地图长m、宽n，以及阈值k
m, n, k = map(int, input().split())
grid = [[0] * n for _ in range(m)]
# 双重循环，构建数位和矩阵
for i in range(m):
for j in range(n):
# 点(i,j)的数位和为i的数位和+j的数位和
grid[i][j] = cal_digit_sum(i) + cal_digit_sum(j)
ans = 0
checklist = [[0] * n for _ in range(m)]
dfs(0, 0, m, n, k, checklist, grid)
print(ans)
java
import java.util.*;
public class Main {
static int[][] DIRECTIONS = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
static int ans = 0;
public static int cal_digit_sum(int n) {
int ans = 0;
while (n != 0) {
ans += n % 10;
n /= 10;
}
return ans;
}
public static void dfs(int i, int j, int m, int n, int k, int[][] checklist, int[][] grid) {
checklist[i][j] = 1;
ans += 1;
for (int[] dir : DIRECTIONS) {
int ni = i + dir[0];
int nj = j + dir[1];
if (ni >= 0 && ni < m && nj >= 0 && nj < n && checklist[ni][nj] == 0 && grid[ni][nj] <= k) {
dfs(ni, nj, m, n, k, checklist, grid);
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
int n = scanner.nextInt();
int k = scanner.nextInt();
int[][] grid = new int[m][n];
int[][] checklist = new int[m][n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
grid[i][j] = cal_digit_sum(i) + cal_digit_sum(j);
}
}
dfs(0, 0, m, n, k, checklist, grid);
System.out.println(ans);
}
}
cpp
#include
#include
using namespace std;
vector
int cal_digit_sum(int n) {
int ans = 0;
while (n != 0) {
ans += n % 10;
n /= 10;
}
return ans;
}
int ans = 0;
void dfs(int i, int j, int m, int n, int k, vector
checklist[i][j] = 1;
ans += 1;
for (auto& dir : DIRECTIONS) {
int ni = i + dir[0];
int nj = j + dir[1];
if (ni >= 0 && ni < m && nj >= 0 && nj < n && checklist[ni][nj] == 0 && grid[ni][nj] <= k) {
dfs(ni, nj, m, n, k, checklist, grid);
}
}
}
int main() {
int m, n, k;
cin >> m >> n >> k;
vector
vector
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
grid[i][j] = cal_digit_sum(i) + cal_digit_sum(j);
}
}
dfs(0, 0, m, n, k, checklist, grid);
cout << ans << endl;
return 0;
}
解法二：BFS
python
# 题目：【DFS/BFS】2023C-地图寻宝
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：BFS
# 代码看不懂的地方，请直接在群上提问
from collections import deque
# 表示四个方向的数组
DIRECTIONS = [(0,1), (1,0), (-1,0), (0,-1)]
# 构建非负整数n的数位和的函数
def cal_digit_sum(n):
ans = 0
while n != 0:
ans += n % 10
n //= 10
return ans
# 输入地图长m、宽n，以及阈值k
m, n, k = map(int, input().split())
grid = [[0] * n for _ in range(m)]
# 双重循环，构建数位和矩阵
for i in range(m):
for j in range(n):
# 点(i,j)的数位和为i的数位和+j的数位和
grid[i][j] = cal_digit_sum(i) + cal_digit_sum(j)
ans = 0
checklist = [[0] * n for _ in range(m)]
checklist[0][0] = 1
q = deque()
q.append((0, 0))
# 进行BFS
while len(q) != 0:
i, j = q.popleft()
ans += 1
for di, dj in DIRECTIONS:
ni, nj = i+di, j+dj
# 注意此处的判断条件为grid[ni][nj] <= k
if 0 <= ni < m and 0 <= nj < n and checklist[ni][nj] == 0 and grid[ni][nj] <= k:
q.append((ni, nj))
checklist[ni][nj] = 1
print(ans)
java
import java.util.*;
public class Main {
static int[][] DIRECTIONS = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
public static int cal_digit_sum(int n) {
int ans = 0;
while (n != 0) {
ans += n % 10;
n /= 10;
}
return ans;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
int n = scanner.nextInt();
int k = scanner.nextInt();
int[][] grid = new int[m][n];
int[][] checklist = new int[m][n];
checklist[0][0] = 1;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
grid[i][j] = cal_digit_sum(i) + cal_digit_sum(j);
}
}
int ans = 0;
Queue
queue.add(new int[]{0, 0});
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; ++i) {
int[] point = queue.poll();
int x = point[0];
int y = point[1];
ans++;
for (int[] dir : DIRECTIONS) {
int nx = x + dir[0];
int ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && checklist[nx][ny] == 0 && grid[nx][ny] <= k) {
queue.add(new int[]{nx, ny});
checklist[nx][ny] = 1;
}
}
}
}
System.out.println(ans);
}
}
cpp
#include
#include
#include
using namespace std;
vector
int cal_digit_sum(int n) {
int ans = 0;
while (n != 0) {
ans += n % 10;
n /= 10;
}
return ans;
}
int main() {
int m, n, k;
cin >> m >> n >> k;
vector
vector
checklist[0][0] = 1;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
grid[i][j] = cal_digit_sum(i) + cal_digit_sum(j);
}
}
int ans = 0;
queue
q.push({0, 0});
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; ++i) {
int x = q.front().first;
int y = q.front().second;
q.pop();
ans++;
for (auto& dir : DIRECTIONS) {
int nx = x + dir[0];
int ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && checklist[nx][ny] == 0 && grid[nx][ny] <= k) {
q.push({nx, ny});
checklist[nx][ny] = 1;
}
}
}
}
cout << ans << endl;
return 0;
}
时空复杂度
时间复杂度：O(NM)。
空间复杂度：O(NM)。
华为OD算法/大厂面试高频题算法练习冲刺训练
华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！ 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！ 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 大厂真题汇总 & OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
精彩链接
发表评论