三个测试用例全部通过以下是 LeetCode LCP 13. 寻宝 的 Python3 实现pythonfrom typing import Listfrom collections import dequeclass Solution:def minimalSteps(self, maze: List[str]) - int:n len(maze)m len(maze[0])# 收集特殊点buttons [] # 机关点 Mstones [] # 石堆点 Ostart Noneend Nonefor i in range(n):for j in range(m):c maze[i][j]if c M:buttons.append((i, j))elif c O:stones.append((i, j))elif c S:start (i, j)elif c T:end (i, j)num_b len(buttons)num_s len(stones)# BFS 计算从 (x, y) 到迷宫中所有其他点的最短距离def bfs(x, y):dist [[-1] * m for _ in range(n)]q deque()dist[x][y] 0q.append((x, y))dirs [(0, 1), (0, -1), (1, 0), (-1, 0)]while q:cx, cy q.popleft()for dx, dy in dirs:nx, ny cx dx, cy dyif 0 nx n and 0 ny m:if maze[nx][ny] ! # and dist[nx][ny] -1:dist[nx][ny] dist[cx][cy] 1q.append((nx, ny))return dist# 计算起点到所有点的距离start_dist bfs(start[0], start[1])# 如果没有机关直接从 S 走到 Tif num_b 0:return start_dist[end[0]][end[1]]# 计算每个机关到所有点的距离button_dists []for i in range(num_b):button_dists.append(bfs(buttons[i][0], buttons[i][1]))# dist[i][num_b] S - O - Mi 的最短距离起点到机关i必须经过石堆# dist[i][num_b1] Mi - T 的最短距离机关i到终点# dist[i][j] Mi - O - Mj 的最短距离机关i到机关j必须经过石堆dist [[-1] * (num_b 2) for _ in range(num_b)]for i in range(num_b):# 机关 i 到终点 Tdist[i][num_b 1] button_dists[i][end[0]][end[1]]# 起点 S 到机关 i必须经过某个石堆min_dist -1for j in range(num_s):sx, sy stones[j]if button_dists[i][sx][sy] ! -1 and start_dist[sx][sy] ! -1:d button_dists[i][sx][sy] start_dist[sx][sy]if min_dist -1 or d min_dist:min_dist ddist[i][num_b] min_dist# 机关 i 到机关 j必须经过某个石堆for j in range(i 1, num_b):min_dist -1for k in range(num_s):sx, sy stones[k]if button_dists[i][sx][sy] ! -1 and button_dists[j][sx][sy] ! -1:d button_dists[i][sx][sy] button_dists[j][sx][sy]if min_dist -1 or d min_dist:min_dist ddist[i][j] min_distdist[j][i] min_dist# 如果有机关无法从起点到达或无法到达终点返回 -1for i in range(num_b):if dist[i][num_b] -1 or dist[i][num_b 1] -1:return -1# 状态压缩 DP# dp[mask][i] 当前处于第 i 个机关已触发机关状态为 mask 的最短步数# mask 的第 j 位为 1 表示第 j 个机关已触发INF float(inf)dp [[INF] * num_b for _ in range(1 num_b)]# 初始化从起点 S 到每个机关for i in range(num_b):dp[1 i][i] dist[i][num_b]# DP 转移for mask in range(1, 1 num_b):for i in range(num_b):if not (mask (1 i)):continueif dp[mask][i] INF:continuefor j in range(num_b):if mask (1 j):continueif dist[i][j] -1:continuenext_mask mask | (1 j)new_dist dp[mask][i] dist[i][j]if new_dist dp[next_mask][j]:dp[next_mask][j] new_dist# 所有机关触发后从最后一个机关走到终点 Tfinal_mask (1 num_b) - 1ans INFfor i in range(num_b):if dp[final_mask][i] INF or dist[i][num_b 1] -1:continuetotal dp[final_mask][i] dist[i][num_b 1]ans min(ans, total)return ans if ans ! INF else -1核心思路步骤 说明BFS 预处理 从 S 和每个 M 分别做 BFS求到全图的最短距离关键点距离计算 枚举石堆 O计算 S→O→M、Mi→O→Mj、M→T 的最短距离状态压缩 DP dp[mask][i] 表示已触发 mask 状态的机关当前在机关 i 的最小步数复杂度分析- 时间复杂度O((1 num_M) × n × m num_M² × num_O 2^num_M × num_M²)- 空间复杂度O((1 num_M) × n × m 2^num_M × num_M) 约束条件num_M ≤ 16num_O ≤ 40n, m ≤ 100状态压缩 DP 完全可行。验证结果测试用例 输入 输出1 [S#O, M.., M.T] 16 ✅2 [S#O, M.#, M.T] -1 ✅3 [S#O, M.T, M..] 17 ✅下载文件: [LCP 13 寻宝 Python3 实现](sandbox:///mnt/agents/output/lcp13_xun_bao.py)
Kimi LeetCode LCP 13. 寻宝 Python3实现
三个测试用例全部通过以下是 LeetCode LCP 13. 寻宝 的 Python3 实现pythonfrom typing import Listfrom collections import dequeclass Solution:def minimalSteps(self, maze: List[str]) - int:n len(maze)m len(maze[0])# 收集特殊点buttons [] # 机关点 Mstones [] # 石堆点 Ostart Noneend Nonefor i in range(n):for j in range(m):c maze[i][j]if c M:buttons.append((i, j))elif c O:stones.append((i, j))elif c S:start (i, j)elif c T:end (i, j)num_b len(buttons)num_s len(stones)# BFS 计算从 (x, y) 到迷宫中所有其他点的最短距离def bfs(x, y):dist [[-1] * m for _ in range(n)]q deque()dist[x][y] 0q.append((x, y))dirs [(0, 1), (0, -1), (1, 0), (-1, 0)]while q:cx, cy q.popleft()for dx, dy in dirs:nx, ny cx dx, cy dyif 0 nx n and 0 ny m:if maze[nx][ny] ! # and dist[nx][ny] -1:dist[nx][ny] dist[cx][cy] 1q.append((nx, ny))return dist# 计算起点到所有点的距离start_dist bfs(start[0], start[1])# 如果没有机关直接从 S 走到 Tif num_b 0:return start_dist[end[0]][end[1]]# 计算每个机关到所有点的距离button_dists []for i in range(num_b):button_dists.append(bfs(buttons[i][0], buttons[i][1]))# dist[i][num_b] S - O - Mi 的最短距离起点到机关i必须经过石堆# dist[i][num_b1] Mi - T 的最短距离机关i到终点# dist[i][j] Mi - O - Mj 的最短距离机关i到机关j必须经过石堆dist [[-1] * (num_b 2) for _ in range(num_b)]for i in range(num_b):# 机关 i 到终点 Tdist[i][num_b 1] button_dists[i][end[0]][end[1]]# 起点 S 到机关 i必须经过某个石堆min_dist -1for j in range(num_s):sx, sy stones[j]if button_dists[i][sx][sy] ! -1 and start_dist[sx][sy] ! -1:d button_dists[i][sx][sy] start_dist[sx][sy]if min_dist -1 or d min_dist:min_dist ddist[i][num_b] min_dist# 机关 i 到机关 j必须经过某个石堆for j in range(i 1, num_b):min_dist -1for k in range(num_s):sx, sy stones[k]if button_dists[i][sx][sy] ! -1 and button_dists[j][sx][sy] ! -1:d button_dists[i][sx][sy] button_dists[j][sx][sy]if min_dist -1 or d min_dist:min_dist ddist[i][j] min_distdist[j][i] min_dist# 如果有机关无法从起点到达或无法到达终点返回 -1for i in range(num_b):if dist[i][num_b] -1 or dist[i][num_b 1] -1:return -1# 状态压缩 DP# dp[mask][i] 当前处于第 i 个机关已触发机关状态为 mask 的最短步数# mask 的第 j 位为 1 表示第 j 个机关已触发INF float(inf)dp [[INF] * num_b for _ in range(1 num_b)]# 初始化从起点 S 到每个机关for i in range(num_b):dp[1 i][i] dist[i][num_b]# DP 转移for mask in range(1, 1 num_b):for i in range(num_b):if not (mask (1 i)):continueif dp[mask][i] INF:continuefor j in range(num_b):if mask (1 j):continueif dist[i][j] -1:continuenext_mask mask | (1 j)new_dist dp[mask][i] dist[i][j]if new_dist dp[next_mask][j]:dp[next_mask][j] new_dist# 所有机关触发后从最后一个机关走到终点 Tfinal_mask (1 num_b) - 1ans INFfor i in range(num_b):if dp[final_mask][i] INF or dist[i][num_b 1] -1:continuetotal dp[final_mask][i] dist[i][num_b 1]ans min(ans, total)return ans if ans ! INF else -1核心思路步骤 说明BFS 预处理 从 S 和每个 M 分别做 BFS求到全图的最短距离关键点距离计算 枚举石堆 O计算 S→O→M、Mi→O→Mj、M→T 的最短距离状态压缩 DP dp[mask][i] 表示已触发 mask 状态的机关当前在机关 i 的最小步数复杂度分析- 时间复杂度O((1 num_M) × n × m num_M² × num_O 2^num_M × num_M²)- 空间复杂度O((1 num_M) × n × m 2^num_M × num_M) 约束条件num_M ≤ 16num_O ≤ 40n, m ≤ 100状态压缩 DP 完全可行。验证结果测试用例 输入 输出1 [S#O, M.., M.T] 16 ✅2 [S#O, M.#, M.T] -1 ✅3 [S#O, M.T, M..] 17 ✅下载文件: [LCP 13 寻宝 Python3 实现](sandbox:///mnt/agents/output/lcp13_xun_bao.py)
