华为OD机试统一考试D卷C卷 - 亲子游戏
题目描述
宝宝和妈妈参加亲子游戏,在一个二维矩阵(N*N)的格子地图上,宝宝和妈妈抽签决定各自的位置,地图上每个格子有不同的糖果数量,部分格子有障碍物。
游戏规则是妈妈必须在最短的时间(每个单位时间只能走一步)到达宝宝的位置,路上的所有糖果都可以拿走,不能走障碍物的格子,只能上下左右走。
请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果(优先考虑最短时间到达的情况下尽可能多拿糖果)。
输入描述
第一行输入为 N,N 表示二维矩阵的大小
之后 N 行,每行有 N 个值,表格矩阵每个位置的值,其中:
- -3:妈妈
- -2:宝宝
- -1:障碍
- ≥0:糖果数(0表示没有糖果,但是可以走)
输出描述
输出妈妈在最短到达宝宝位置的时间内最多拿到多少糖果,行末无多余空格
用例
输入
4
3 2 1 -3
1 -1 1 1
1 1 -1 2
-2 1 2 3
输出
9
说明
此地图有两条最短路径可到达宝宝位置,绿色线和黄色线都是最短路径6步,但黄色拿到的糖果更多,9个。
输入
4
3 2 1 -3
-1 -1 1 1
1 1 -1 2
-2 1 -1 3
输出
-1
说明
此地图妈妈无法到达宝宝位置
Java
import java.util.*;
// 主类
public class Main {
// 定义四个方向移动的坐标变化(上、右、下、左)
private static final int[] dx = {-1, 0, 1, 0};
private static final int[] dy = {0, 1, 0, -1};
// 主函数
public static void main(String[] args) {
// 使用 Scanner 读取输入数据
Scanner scanner = new Scanner(System.in);
// 读取矩阵的大小
int N = scanner.nextInt();
// 初始化矩阵
int[][] grid = new int[N][N];
// 初始化访问数组,记录到达每个位置的最短步数和糖果数量
int[][][] visited = new int[N][N][2]; // [x][y][0] 代表步数,[x][y][1] 代表糖果数
// 将访问数组初始化为 -1
for (int[][] layer : visited) {
for (int[] cell : layer) {
Arrays.fill(cell, -1);
}
}
// 初始化队列,用于 BFS 搜索
Queue<Node> queue = new LinkedList<>();
// 初始化起点
Node start = null;
// 读取矩阵信息,并找到起点位置
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
grid[i][j] = scanner.nex
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2024华为OD机试E卷D卷题 文章被收录于专栏
本专栏给大家提供了华为2024最新华为OD(D)卷的题目汇总。华为OD机试刷题记录机考算法题库,帮助你上岸华为。提供C++/Java、JavaScript、Python四种语言的解法。