阅读量:0
2024华为OD机试题库-(C卷+D卷)-(JAVA、Python、C++)
题目描述
宝宝和妈妈参加亲子游戏，在一个二维矩阵（N*N）的格子地图上，宝宝和妈妈抽签决定各自的位置，地图上每个格子有不同的糖果数量，部分格子有障碍物。
游戏规则是妈妈必须在最短的时间（每个单位时间只能走一步）到达宝宝的位置，路上的所有糖果都可以拿走，不能走障碍物的格子，只能上下左右走。
请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果（优先考虑最短时间到达的情况下尽可能多拿糖果）。
输入描述
第一行输入为 N，N 表示二维矩阵的大小
之后 N 行，每行有 N 个值，表格矩阵每个位置的值，其中：
- -3：妈妈
- -2：宝宝
- -1：障碍
- ≥0：糖果数（0表示没有糖果，但是可以走）
输出描述
输出妈妈在最短到达宝宝位置的时间内最多拿到多少糖果，行末无多余空格
备注
地图最大 50*50
用例1
输入
4
3 2 1 -3
1 -1 1 1
1 1 -1 2
-2 1 2 3
输出
9
解题思路
本题可以使用bfs广度优先算法求解，从妈妈开始的位置向四周扩散，如果周围的空格未被走过，且不是墙，就可以进入该空格，并且用一个矩阵 记录每个非墙的空格处获得的糖果个数。最后当可以到达宝宝位置的层遍历结束时，宝宝所在位置获得的最多糖果数即为最短路径的最多糖果数。
代码
c++
#include <bits/stdc++.h> using namespace std; int main() { int n; cin>>n; int res=-1; int mat[n][n];//格子地图 int sx,sy;//妈妈出发的坐标 vector<vector<int>> candy(n,vector<int>(n,-1));//存放每个格子处能得到糖果的个数，初始化为-1 for(int i=0;i<n;i++) { for(int