S4-迷宫探索（2026年1月）

# 🏫 校园迷宫寻宝 | 巅峰赛编程题目 ## 🎯 题目背景 学校的科技节到了，有一个特别的迷宫寻宝游戏。迷宫是一个 `m × n` 的网格，每个格子里有一个数字，表示进入这个格子需要消耗的**能量值**。小智同学从左上角(0,0)出发，需要到达右下角(m-1,n-1)的宝藏位置。 好消息是，小智有一个神奇的**能量护盾**，使用一次可以**完全抵挡**一个格子的能量消耗（使该格子能量值变为0），但这个护盾只能使用一次，且不能在起点和终点使用。 小智每次只能**向右**或**向下**移动。请你帮助小智计算出到达宝藏位置所需的最少能量消耗。 ## 📋 题目要求 编写一个函数 `min_energy(grid)`，接受一个参数： - `grid`：一个 `m × n` 的二维整数列表，表示迷宫的能量值网格 函数需要返回一个整数，表示小智到达宝藏位置所需的**最少能量消耗**。 ## 🎮 游戏规则 1. 从左上角(0,0)出发，只能向右或向下移动 2. 每个格子的数字表示进入该格子消耗的能量值 3. 有一个能量护盾，可以使用一次，使**任意一个**非起点非终点的格子能量消耗变为0 4. 护盾只能使用一次 5. 目标是到达右下角(m-1,n-1) ## 🔍 数据范围 - 1 ≤ m, n ≤ 50 - 1 ≤ grid[i][j] ≤ 100 ## 💡 示例测试 ### 示例 1 ```python 输入： grid = [ [1, 3, 1], [1, 5, 1], [4, 2, 1] ] 输出：6 解释： 最优路径：1→3→5→1→1 使用护盾在数字5的格子上，实际消耗：1+3+0+1+1=6 如果不使用护盾，最小消耗是1+3+1+1+1=7 ``` ### 示例 2 ```python 输入： grid = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] 输出：21 解释： 最优路径：1→2→3→6→9 使用护盾不会减少总消耗（因为护盾用在较小的数字上不划算） 最小消耗：1+2+3+6+9=21 ``` ### 示例 3 ```python 输入： grid = [ [5, 5, 5], [5, 5, 5], [5, 5, 5] ] 输出：20 解释： 任意路径都需要经过5个格子 使用护盾跳过一个5的消耗：5+5+0+5+5=20 不使用护盾：5+5+5+5+5=25 ``` ### 示例 4 ```python 输入： grid = [ [1, 100, 100], [100, 1, 100], [100, 100, 1] ] 输出：3 解释： 最优路径：1→100→1→100→1 使用护盾在两个100中选一个，实际消耗：1+0+1+100+1=103 等等，还有更好的！ 走对角线：1→1→1（需要护盾吗？） 实际上无法只走对角线，必须向右或向下移动 正确的最优路径：1→100→1→100→1，护盾用在第一个100上：1+0+1+100+1=103 或者护盾用在第二个100上：1+100+1+0+1=103 不对，让我们重新思考... 找到更好的路径：先向右到100，再向下到1，再向右到100，再向下到1 路径上的值：1, 100, 1, 100, 1，护盾用在一个100上：103 等等，也许有路径可以避开一些100？ 从(0,0)到(2,2)必须经过5个格子，其中3个1和2个100 使用护盾将一个100变为0：1+1+1+0+1=4 但是这样的路径存在吗？ 让我们重新设计这个测试用例... ``` 让我修正示例4： ### 示例 4（修正版） ```python 输入： grid = [ [1, 2], [3, 4] ] 输出：5 解释： 路径1→2→4，护盾用在2上：1+0+4=5 或者路径1→3→4，护盾用在3上：1+0+4=5 ``` ### 示例 5 ```python 输入： grid = [ [1] ] 输出：1 解释： 只有一个格子，起点就是终点 不能使用护盾（起点和终点不能用护盾） 消耗就是1 ``` ## 📝 函数模板 ```python def min_energy(grid): """ 计算到达宝藏位置的最少能量消耗 参数: grid -- 二维整数列表，表示迷宫的能量值 返回: 最少能量消耗 """ # 你的代码在这里 pass ``` ## 🧠 解题提示 1. 这是一个动态规划问题 2. 考虑两种状态：使用过护盾和未使用过护盾 3. 对于每个格子，计算两种状态下的最小消耗 4. 注意边界条件（第一行和第一列） 5. 护盾不能在起点和终点使用 ## 🔧 算法思路 我们可以使用两个二维数组来记录状态： - `dp0[i][j]`：到达(i,j)时**未使用**护盾的最小消耗 - `dp1[i][j]`：到达(i,j)时**已使用**护盾的最小消耗 状态转移： 1. 对于`dp0`：只能从未使用护盾的状态转移过来 2. 对于`dp1`：有两种可能 - 之前已经使用过护盾，现在正常走 - 之前未使用护盾，现在在这个格子使用护盾 ## 📊 状态转移方程 设当前格子能量值为`grid[i][j]` ``` # 未使用护盾到达(i,j) dp0[i][j] = min(dp0[i-1][j], dp0[i][j-1]) + grid[i][j] # 已使用护盾到达(i,j) dp1[i][j] = min( # 之前已使用护盾，现在正常走 min(dp1[i-1][j], dp1[i][j-1]) + grid[i][j], # 之前未使用护盾，现在在这个格子使用护盾（跳过当前消耗） min(dp0[i-1][j], dp0[i][j-1]) ) ``` 注意：起点(0,0)不能使用护盾，所以`dp1[0][0]`应设为一个很大的数 ## 🎓 评分标准 - ✅ 正确计算最少能量消耗（60分） - ✅ 处理边界情况（20分） - ✅ 代码简洁高效，有适当的注释（20分） ## 🌟 温馨提示 1. 注意网格大小为1×1的特殊情况 2. 注意第一行和第一列的特殊处理 3. 护盾只能使用一次，且不能在起点和终点使用 4. 可以先思考不使用护盾的情况，再考虑使用护盾的情况 --- **💪 挑战开始！** 运用你的动态规划知识，帮助小智用最少的能量找到宝藏吧！记得仔细分析状态转移，确保覆盖所有可能的情况！