亲子游戏 - 华为OD统一考试(D卷)

OD统一考试（D卷）

分值： 200分

题解： Java / Python / C++

alt

题目描述

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

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

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

输入描述

第一行输入为 N，N 表示二维矩阵的大小。之后 N 行，每行有 N 个值，表格矩阵每个位置的值，其中:

-3: 妈妈
-2: 宝宝
-1: 障碍
$\geq 0$ : 糖果数(0 表示没有糖果，但是可以走)

输出描述

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

备注

地图最大 50 * 50

示例1

输入：
4
3 2 1 -3
1 -1 1 1
1 1 -1 2
-2 1 2 3

输出：
9

说明：
此地图有两条最短路径可到达宝宝位置，绿色线和黄色线都是最短路径6步，但黄色拿到的糖果更多，9个。

示例2

输入：
4
3 2 1 -3
-1 -1 1 1
1 1 -1 2
-2 1 -1 3

输出：
-1

说明：
此地图妈妈无法到达宝宝的位置。

题解

这道题是一个经典的 BFS（广度优先搜索）问题。妈妈需要在最短时间内从起点到达终点，并且在这个过程中尽可能多地收集糖果。可以通过 BFS 来同时处理路径最短和糖果最多的问题。

解题思路

数据结构选择：

使用 Deque（双端队列）来进行 BFS 搜索。

使用一个二维数组 vis 来标记访问过的节点。

初始化：

从起点位置开始，初始化 Deque，并把起点加入队列。

记录妈妈和宝宝的起始位置。

BFS 搜索：

每次从队列中取出当前节点，检查是否到达终点。

如果到达终点，更新最大糖果数量并标记为已找到结果。

否则，将当前格子的糖果数加到总糖果数中。

向四个方向探索相邻节点，将有效的节点加入队列。

终止条件：

如果队列为空，说明所有可行路径已经探索完毕。

如果找到了终点，记录结果并输出。

复杂度分析

时间复杂度：O(N^2)，其中 N 是矩阵的大小，因为每个格子最多访问一次。

空间复杂度：O(N^2)，用于存储队列和访问标记数组。

Java

import java.util.*;
/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] grid = new int[n][n];

        int sr = 0, sc = 0, tr = 0, tc = 0;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                grid[r][c] = in.nextInt();
                if (grid[r][c] == -3) { // 妈妈的位置
                    sr = r;
                    sc = c;
                } else if (grid[r][c] == -2) { // 宝宝的位置
                    tr = r;
                    tc = c;
                }
            }
        }

        // <拿到的糖果, 横坐标, 纵坐标>
        Deque<int[]> dq = new ArrayDeque<>();
        boolean[][] vis = new boolean[n][n];
        dq.offer(new int[]{0, sr, sc});

        boolean hasResult = false; // 是否已经到达宝宝的位置
        int maxAns = -1; // 妈妈在最短到达宝宝位置的时间内最多拿到多少糖果
        int[] dirs = {-1, 0, 1, 0, -1};
        while (!dq.isEmpty() && !hasResult) {
            int size = dq.size();
            for (int i = 0; i < size; i++) {
                int[] pii = dq.poll();
                int tot = pii[0], r = pii[1], c = pii[2];
                vis[r][c] = true;

                // 到达终点
                if (r == tr && c == tc) {
                    hasResult = true;
                    maxAns = Math.max(maxAns, tot);
                }

                // 拿到当前位置的糖果
                if (grid[r][c] > 0) tot += grid[r][c];

                // 向四周探索
                for (int j = 1; j < 5; j++) {
                    int nr = r + dirs[j - 1], nc = c + dirs[j];
                    if (nr < 0 || nc < 0 || nr >= n || nc >= n || vis[nr][nc] || grid[nr][nc] == -1)
                        continue;

                    dq.offer(new int[]{tot, nr, nc});
                }
            }
        }

        System.out.println(maxAns);
    }
}

Python

from collections import deque

def main():
    n = int(input())
    grid = []
    for _ in range(n):
        grid.append(list(map(int, input().split())))

    sr, sc, tr, tc = 0, 0, 0, 0
    for r in range(n):
        for c in range(n):
            if grid[r][c] == -3: # 妈妈的位置
                sr, sc = r, c
            elif grid[r][c] == -2: # 宝宝的位置
                tr, tc = r, c

    # （拿到的糖果，横坐标, 纵坐标）
    dq = deque([(0, sr, sc)])
    vis = [[False] * n for _ in range(n)]

    hasResult = False # 是否已经到达宝宝的位置
    maxAns = -1 # 妈妈在最短到达宝宝位置的时间内最多拿到多少糖果
    dirs = [-1, 0, 1, 0, -1]
    while dq and not hasResult:
        size = len(dq)
        for _ in range(size):
            tot, r, c = dq.popleft()
            vis[r][c] = True

            # 到达终点
            if r == tr and c == tc:
                hasResult = True
                maxAns = max(maxAns, tot)

            # 拿到当前位置的糖果
            if grid[r][c] > 0:
                tot += grid[r][c]

            # 向四周探索
            for j in range(1, 5):
                nr, nc = r + dirs[j - 1], c + dirs[j]
                if nr < 0 or nc < 0 or nr >= n or nc >= n or vis[nr][nc] or grid[nr][nc] == -1:
                    continue

                dq.append((tot, nr, nc))

    print(maxAns)

if __name__ == "__main__":
    main()

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> grid(n, vector<int>(n));

    int sr, sc, tr, tc;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            cin >> grid[r][c];
            if (grid[r][c] == -3) {   // 妈妈的位置
                sr = r;
                sc = c;
            } else if (grid[r][c] == -2) {   // 宝宝的位置
                tr = r;
                tc = c;
            }
        }
    }

    // <拿到的糖果，<横坐标, 纵坐标>>
    deque<pair<int, pair<int, int>>> dq;
    vector<vector<bool>>             vis(n, vector(n, false));
    dq.push_back({0, {sr, sc}});

    bool hasResult = false;   // 是否已经到达宝宝的位置
    int  maxAns    = -1;   // 妈妈在最短到达宝宝位置的时间内最多拿到多少糖果
    int  dirs[]    = {-1, 0, 1, 0, -1};
    while (!dq.empty() && !hasResult) {
        size_t size = dq.size();
        for (size_t i = 0; i < size; i++) {
            auto pii = dq.front();
            dq.pop_front();
            int tot = pii.first, r = pii.second.first, c = pii.second.second;
            vis[r][c] = true;

            // 到达终点
            if (r == tr && c == tc) {
                hasResult = true;
                maxAns    = max(maxAns, tot);
            }

            // 拿到当前位置的糖果
            if (grid[r][c] > 0) tot += grid[r][c];

            // 向四周探索
            for (int j = 1; j < 5; j++) {
                int nr = r + dirs[j - 1], nc = c + dirs[j];
                if (nr < 0 || nc < 0 || nr >= n || nc >= n || vis[nr][nc] || grid[nr][nc] == -1)
                    continue;

                dq.push_back({tot, {nr, nc}});
            }
        }
    }

    cout << maxAns << endl;

    return 0;
}