【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

            示例一

            输入

            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
            

            说明

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

            解题思路

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

            代码

            Python

            # 题目：【BFS】2023C-亲子游戏
            # 分值：200
            # 作者：许老师-闭着眼睛学数理化
            # 算法：BFS
            # 代码看不懂的地方，请直接在群上提问
            from collections import deque
            from 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，找到最短路径长度level
            while 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