刷题笔记合集🔗

亲子游戏

问题描述

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

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

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

输入格式

第一行输入为 ， 表示二维矩阵的大小。

之后 行，每行有 个值，表格矩阵每个位置的值，其中：

• ：小柯
• ：孩子
• ：障碍
• ：糖果数（ 表示没有糖果，但是可以走）

输出格式

输出小柯在最短到达孩子位置的时间内最多拿到多少糖果。

样例输入

4
3 2 1 -3
1 -1 1 1
1 1 -1 2
-2 1 2 3

4
3 2 1 -3
-1 -1 1 1
1 1 -1 2
-2 1 -1 3

样例输出

9

-1

数据范围

• 地图最大

题解

这道题是一个典型的广度优先搜索（BFS）问题，我们需要找到从小柯到达孩子位置的最短路径，并且在所有最短路径中选择能够获取最多糖果的路径。

首先，理解问题本质：

1. 需要找到最短路径（步数最少）
2. 在所有最短路径中，选择能拿到最多糖果的路径

BFS非常适合解决这类问题，因为它按照"层"来扩展搜索，第一次到达目标点时的路径就是最短路径。但是本题还需要考虑糖果的优化，所以我们需要稍微修改一下传统的BFS。

解题思路如下：

1. 使用BFS从小柯的位置开始搜索
2. 维护一个二维数组candy，记录到达每个点时能收集到的最大糖果数
3. 初始化candy数组为-1，表示该位置尚未被访问
4. 每次向四个方向扩展时，如果新位置可以访问，更新该位置能收集到的最大糖果数
5. 当BFS第一次到达孩子位置时，我们就找到了最短路径
6. 需要继续遍历当前层的所有节点，确保找到最短路径中糖果最多的路径

代码实现的关键点：

• 使用队列进行BFS，按层扩展
• 使用candy数组记录到达每个位置时的最大糖果数
• 当发现一条通往孩子的路径时，记录下糖果数并继续遍历当前层
• 如果无法到达孩子位置，返回-1

时间复杂度分析：

• BFS最坏情况下需要访问地图中的每个格子，时间复杂度为O(N²)
• 空间复杂度也是O(N²)，主要用于存储队列和candy数组

由于地图最大为50*50，N²最大为2500，这个复杂度对于给定的数据范围是完全可以接受的。

参考代码

• Python

import sys
from collections import deque

def main():
    # 读取输入
    n = int(sys.stdin.readline())
    grid = []
    candy = [[-1 for _ in range(n)] for _ in range(n)]  # 记录到每个位置的最大糖果数
    q = deque()
    
    # 读取地图并找到小柯位置
    for i in range(n):
        row = list(map(int, sys.stdin.readline().split()))
        grid.append(row)
        for j in range(n):
            if grid[i][j] == -3:
                candy[i][j] = 0  # 初始无糖果
                q.append((i, j))
    
    ans = -1
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 四个移动方向
    
    # BFS开始
    while q:
        size = len(q)
        found = False
        next_level = []
        
        # 处理当前层
        for _ in range(size):
            x, y = q.popleft()
            
            # 向四个方向扩展
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                
                # 检查边界和障碍物
                if nx < 0 or nx >= n or ny < 0 or ny >= n or grid[nx][ny] == -1:
                    continue
                
                # 计算新的糖果总数
                new_candy = candy[x][y]
                if grid[nx][ny] > 0:
                    new_candy += grid[nx][ny]
                
                # 如果是新位置或者有更多糖果
                if candy[nx][ny] == -1 or new_candy > candy[nx][ny]:
                    candy[nx][ny] = new_candy
                    next_level.append((nx, ny))
                    
                    # 如果找到孩子
                    if grid[nx][ny] == -2:
                        ans = max(ans, new_candy)
                        found = True
        
        # 如果在当前层找到孩子，不再继续扩展
        if found:
            break
        
        # 将下一层节点加入队列
        for p in next_level:
            q.append(p)
    
    print(ans)

if __name__ == "__main__":
    main()

• Cpp

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

int main() {
    int n;
    cin >> n;
    
    vector<vector<int>> grid(n, vector<int>(n));
    vector<vector<int>> candy(n, vector<int>(n, -1)); // 记录到每个位置的最大糖果数
    
    queue<pair<int