一、题目题目描述宝宝和妈妈参加亲子游戏在一个二维矩阵N*N的格子地图上宝宝和妈妈抽签决定各自的位置地图上每个格子有不同的糖果数量部分格子有障碍物。游戏规则是妈妈必须在最短的时间每个单位时间只能走一步到达宝宝的位置路上的所有糖果都可以拿走不能走障碍物的格子只能上下左右走。请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果优先考虑最短时间到达的情况下尽可能多拿糖果。输入描述第一行输入为 NN 标识二维矩阵的大小之后 N 行每行有 N 个值表格矩阵每个位置的值其中-3妈妈-2宝宝-1障碍0糖果数0 表示没有糖果但是可以走≥0糖果数(0表示没有糖果但是可以走)输出描述输出妈妈在最短到达宝宝位置的时间内最多拿到多少糖果行末无多余空格备注地图最大 50*50示例1输入43 2 1 -31 -1 1 11 1 -1 2-2 1 2 3输出9说明此地图有两条最短路径可到宝宝位置都是最短路径6步但先向下再向左可以拿到9个糖果示例2输入43 2 1 -3-1 -1 1 11 1 -1 2-2 1 -1 3输出-1说明此地图妈妈无法到达宝宝位置二、题目深度解析1. 问题本质这是一个典型的双目标最短路问题主目标最小化步数Time。次目标最大化糖果数Candy。由于地图边权均为 1上下左右走一步BFS广度优先搜索是保证步数最小的天然选择。但标准 BFS 一旦访问过某个节点就会标记为visited并不再处理这会导致我们错过“步数相同但糖果更多”的路径。2. 改进策略状态松弛 (Relaxation)我们需要维护两个二维数组dist[x][y]到达(x, y)的最小步数。初始化为INF。max_candy[x][y]在最小步数前提下到达(x, y)的最大糖果数。初始化为-1。核心逻辑流转当从节点u扩展到邻居v时更短路径发现(dist[v] dist[u] 1)更新dist[v]和max_candy[v]。v入队。等长更优路径发现(dist[v] dist[u] 1且new_candy max_candy[v])仅更新max_candy[v]。关键操作v必须再次入队原因v的糖果基数变大了它传递给后续节点的累积糖果数也会变大。如果不重新入队后续节点将基于旧的、较小的值计算导致最终结果非最优。3. 为什么不会死循环虽然允许重复入队但每个节点的max_candy值是单调递增的。由于地图中糖果总数有限且网格大小固定 (50×50 )每个节点的更新次数是有上限的。在实际测试中这种“类 SPFA”的 BFS 变种收敛极快。三、C 极致实现 (C11/14 标准)本代码采用了以下优化技巧IO 加速ios::sync_with_stdio(0); cin.tie(0);关闭同步流大幅提升读取速度。结构体封装使用struct Node替代pair语义更清晰。常量定义使用constexpr定义方向数组和无穷大编译器可进一步优化。内存预分配vector提前resize避免动态扩容开销。#include iostream #include vector #include queue #include tuple using namespace std; // 定义无穷大表示不可达 const int INF 1e9; // 方向数组上、下、左、右 const int dx[4] {-1, 1, 0, 0}; const int dy[4] {0, 0, -1, 1}; struct Point { int x, y; Point(int _x, int _y) : x(_x), y(_y) {} }; void solve() { int n; if (!(cin n)) return; vectorvectorint grid(n, vectorint(n)); int startX -1, startY -1; int endX -1, endY -1; // 读取矩阵并定位起点(-3)和终点(-2) for (int i 0; i n; i) { for (int j 0; j n; j) { cin grid[i][j]; if (grid[i][j] -3) { startX i; startY j; } else if (grid[i][j] -2) { endX i; endY j; } } } // 边界情况如果没有起点或终点理论上题目保证有但防御性编程 if (startX -1 || endX -1) { cout -1 endl; return; } // dist[i][j]: 到达 (i,j) 的最短步数 vectorvectorint dist(n, vectorint(n, INF)); // max_candy[i][j]: 在最短步数下到达 (i,j) 的最大糖果数 vectorvectorint max_candy(n, vectorint(n, -1)); queuePoint q; // 初始化起点 dist[startX][startY] 0; max_candy[startX][startY] 0; // 起点本身不计糖果 q.push(Point(startX, startY)); while (!q.empty()) { Point curr q.front(); q.pop(); int cx curr.x; int cy curr.y; // 尝试向四个方向扩展 for (int i 0; i 4; i) { int nx cx dx[i]; int ny cy dy[i]; // 1. 边界检查 if (nx 0 || nx n || ny 0 || ny n) continue; // 2. 障碍物检查 (-1 为障碍) if (grid[nx][ny] -1) continue; // 计算新状态的步数和糖果 int new_step dist[cx][cy] 1; int gain (grid[nx][ny] 0) ? grid[nx][ny] : 0; // 只有 0 才是糖果 int new_candy max_candy[cx][cy] gain; // 情况 A: 发现更短的路径 if (new_step dist[nx][ny]) { dist[nx][ny] new_step; max_candy[nx][ny] new_candy; q.push(Point(nx, ny)); } // 情况 B: 路径长度相同但发现了更多的糖果 else if (new_step dist[nx][ny] new_candy max_candy[nx][ny]) { max_candy[nx][ny] new_candy; // 重要糖果数更新了需要重新入队以便将更大的糖果数传递给后续节点 q.push(Point(nx, ny)); } } } // 判断终点是否可达 if (dist[endX][endY] INF) { cout -1 endl; } else { cout max_candy[endX][endY] endl; } } int main() { // C 输入输出加速应对大数据量输入 ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }✅ C 版代码亮点解析ios::sync_with_stdio(false); cin.tie(nullptr);这是 C 刷题的标配。默认情况下cin与 C 风格的scanf同步效率较低。关闭同步后cin的速度可提升数倍防止因输入耗时过长导致 TLE (Time Limit Exceeded)。vectorvectorintvs 原生数组虽然原生数组int grid[55][55]更快但vector更安全且符合现代 C 规范。鉴于题目 N≤50 vector的微小开销完全可以忽略且能自动管理内存避免栈溢出风险。结构体Point相比pairint, int自定义结构体让x和y的语义更明确代码可读性更强且编译器优化后二者性能无异。逻辑严密性严格区分了grid[nx][ny] 0的糖果获取逻辑正确处理了-3(妈妈) 和-2(宝宝) 不作为糖果计数的细节。四、逻辑推演与正确性证明为了让大家彻底放心“重复入队”的逻辑我们做一个简单的推导假设场景节点P可以通过两条路径到达步数均为 K 。路径 1 带来糖果 C110 。路径 2 带来糖果 C220 。执行流程BFS 先处理路径 1。dist[P]K,max_candy[P]10。P入队。P出队用它当前的糖果值 1010 去更新邻居Q。假设Q有 5 个糖果则Q暂时记录为 10515 。BFS 随后处理路径 2。发现dist[P]K但 2010。更新max_candy[P]20。P再次入队。P第二次出队。此时它带着 20 个糖果。P再次更新邻居Q。发现新值 2052515 。更新Q为 25 Q入队。结论通过允许P在“同层更优”时再次入队我们成功地将局部最优解20传播到了全局确保了最终答案的正确性。五、避坑指南 (C 特有)⚠️endlvs\n在循环输出中尽量用\n。虽然本题只输出一次但在大规模数据测试中endl会强制刷新缓冲区显著降低性能。本代码仅在最后输出使用endl无影响。整数溢出题目中 N≤50 单个格子糖果数未说明上限但通常较小总糖果数不会超过int范围 (21亿)。如果题目糖果数极大需改用long long。本题int足矣。起点/终点数值陷阱再次强调不要把-3和-2加到结果里很多初学者会直接sum grid[nx][ny]导致结果错误。代码中(grid[nx][ny] 0) ? ... : 0是关键。六、复杂度分析时间复杂度 O(K⋅N2)N为地图边长。K为每个节点的平均入队次数。在网格图中 K 通常是一个很小的常数一般不超过 4-5 次。对于 N50 总运算量极低远小于 107 次/秒的限制。空间复杂度 O(N2)用于存储grid,dist,max_candy三个二维数组以及队列。50×50×4 bytes×3≈30 KB 内存占用极小。七、结语C 以其运行效率高、控制粒度细的特点成为算法竞赛和大厂机考的首选语言。通过这道题我们不仅掌握了BFS 贪心更新的核心套路还实践了 C 的IO 加速和STL 容器的最佳用法。Java/Go 选手可以参考 C 的状态更新逻辑语言虽不同算法思想互通。Python/JS 选手可以感受 C 在类型安全和内存控制上的严谨性。掌握这一模板无论是面对华为 OD 的“亲子游戏”还是其他变种的最短路问题都能一击必中觉得有帮助请点赞、收藏⭐、关注下一期我们将挑战更高难度的DFS 回溯 剪枝专题