【Py/Java/C++三种语言OD2023C卷真题】20天拿下华为OD笔试之【BFS+DP】2023C-亲子游戏【欧弟算法】全网注释最详细分类最全的华为OD真题题解

文章目录

• 题目描述与示例
• • 题目描述
  • **输入描述**
  • **输出描述**
  • **备注**
  • **示例一**
  • • **输入**
    • **输出**
    • **说明**
    • **示例二**
    • • **输入**
      • **输出**
      • **说明**
      • 解题思路
      • 代码
      • • Python
        • Java
        • C++
        • 时空复杂度
        • 华为OD���法/大厂面试高频题算法练习冲刺训练

          题目描述与示例

          题目描述

          宝宝和妈妈参加亲子游戏，在一个二维矩阵（N*N）的格子地图上，宝宝和妈妈抽签决定各自的位置，地图上每个格子有不同的糖果数量，部分格子有障碍物。

          （）

          游戏规则是妈妈必须在最短的时间（每个单位时间只能走一步）到达宝宝的位置，路上的所有糖果都可以拿走，不能走障碍物的格子，只能上下左右走。

          请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果（优先考虑最短时间到达的情况下尽可能多拿糖果）。

          （）

          输入描述

          第一行输入为N，N标识二维矩阵的大小

          之后N行，每行有N个值，表格矩阵每个位置的值

          其中：

          • -3：妈妈
          • -2：宝宝
          • -1：障碍
          • >=0：糖果数(0表示没有糖果，但是可以走)

            输出描述

            输出妈妈在最短到达宝宝位置的时间内最多拿到多少糖果，行末无多余空格

            备注

            地图最大50*50

            示例一

            输入

            43 2 1 -31 -1 1 11 1 -1 2-2 1 2 3

            输出

            9

            说明

            此地图有两条最短路径可到宝宝位置，都是最短路径6步，但先向下再向左可以拿到9个糖果

            示例二

            输入

            43 2 1 -3-1 -1 1 11 1 -1 2-2 1 -1 3

            输出

            -1

            说明

            此地图妈妈无法到达宝宝位置

            解题思路

            最短路径很容易使用BFS计算得到。本题难点在于如何计算最短路径下的最多糖果。

            代码

            Python

            # 题目：【BFS】2023C-亲子游戏# 分值：200# 作者：许老师-闭着眼睛学数理化# 算法：BFS# 代码看不懂的地方，请直接在群上提问from collections import dequefrom math import inf# 表示4个方向的方向数组DIERECTIONS = DIRECTIONS = [(0,1), (1,0), (-1,0), (0,-1)]# 输入地图边长n = int(input())grid = list()# 循环n行，输入地图for _ in range(n):    grid.append(list(map(int, input().split())))for i in range(n):    for j in range(n):        # 找到妈妈所在的位置，作为起点        if grid[i][j] == -3:            sx, sy = i, j        # 找到孩子所在的位置，作为起点        if grid[i][j] == -2:            tx, ty = i, j# BFS搜索层数，初始化为0，用于表示最短路径长度level = 0# 是否找到孩子的标记isFind = False# 检查数组check_list = [[0] * n for _ in range(n)]check_list[sx][sy] = 1# 维护BFS过程的队列q = deque()q.append((sx, sy))# 进行第一次BFS，找到最短路径长度levelwhile q:    qSize = len(q)    # 当前搜索层的每一个节点    for _ in range(qSize):        x, y = q.popleft()        # 如果当前点是孩子，直接退出循环        if grid[x][y] == -2:            isFind = True            break        # 遍历四个方向        for dx, dy in DIRECTIONS:            nx, ny = x+dx, y+dy            # 判断是否越界、是否已进入、在矩阵中的值            if 0     static int[][] DIRECTIONS = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int n = scanner.nextInt();        int[][] grid = new int[n][n];        int sx = 0, sy = 0, tx = 0, ty = 0;        for (int i = 0; i = 0 && nx = 0 && ny  
            C++
             
            #include #include #include using namespace std;const vector DIRECTIONS = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};int main() {    int n;    cin >> n;    vector grid(n, vector(n));    int sx = 0, sy = 0, tx = 0, ty = 0;    for (int i = 0; i > grid[i][j];            if (grid[i][j] == -3) {                sx = i;                sy = j;            }            if (grid[i][j] == -2) {                tx = i;                ty = j;            }        }    }    int level = 0;    bool isFind = false;    vector checkList(n, vector(n, 0));    checkList[sx][sy] = 1;    queue q;    q.push({sx, sy});    while (!q.empty()) {        int qSize = q.size();        for (int i = 0; i = 0 && nx = 0 && ny = 0 && ny