Kimi LeetCode LCP 13. 寻宝 Golang实现

以下是 LeetCode LCP 13. 寻宝 的 Go 实现gopackage mainimport (math)func minimalSteps(maze []string) int {n : len(maze)m : len(maze[0])// 收集特殊点buttons : make([][2]int, 0) // 机关点 Mstones : make([][2]int, 0) // 石堆点 Ovar start, end [2]intfor i : 0; i n; i {for j : 0; j m; j {switch maze[i][j] {case M:buttons append(buttons, [2]int{i, j})case O:stones append(stones, [2]int{i, j})case S:start [2]int{i, j}case T:end [2]int{i, j}}}}numB : len(buttons)numS : len(stones)// BFS 计算从 (x, y) 到迷宫中所有其他点的最短距离bfs : func(x, y int) [][]int {dist : make([][]int, n)for i : range dist {dist[i] make([]int, m)for j : range dist[i] {dist[i][j] -1}}queue : make([][2]int, 0)dist[x][y] 0queue append(queue, [2]int{x, y})dirs : [4][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}for head : 0; head len(queue); head {cx, cy : queue[head][0], queue[head][1]for _, d : range dirs {nx, ny : cxd[0], cyd[1]if nx 0 nx n ny 0 ny m {if maze[nx][ny] ! # dist[nx][ny] -1 {dist[nx][ny] dist[cx][cy] 1queue append(queue, [2]int{nx, ny})}}}}return dist}// 计算起点到所有点的距离startDist : bfs(start[0], start[1])// 如果没有机关直接从 S 走到 Tif numB 0 {return startDist[end[0]][end[1]]}// 计算每个机关到所有点的距离buttonDists : make([][][]int, numB)for i : 0; i numB; i {buttonDists[i] bfs(buttons[i][0], buttons[i][1])}// dist[i][numB] S - O - Mi 的最短距离起点到机关i必须经过石堆// dist[i][numB1] Mi - T 的最短距离机关i到终点// dist[i][j] Mi - O - Mj 的最短距离机关i到机关j必须经过石堆dist : make([][]int, numB)for i : range dist {dist[i] make([]int, numB2)for j : range dist[i] {dist[i][j] -1}}for i : 0; i numB; i {// 机关 i 到终点 Tdist[i][numB1] buttonDists[i][end[0]][end[1]]// 起点 S 到机关 i必须经过某个石堆minDist : -1for j : 0; j numS; j {sx, sy : stones[j][0], stones[j][1]if buttonDists[i][sx][sy] ! -1 startDist[sx][sy] ! -1 {d : buttonDists[i][sx][sy] startDist[sx][sy]if minDist -1 || d minDist {minDist d}}}dist[i][numB] minDist// 机关 i 到机关 j必须经过某个石堆for j : i 1; j numB; j {minDist -1for k : 0; k numS; k {sx, sy : stones[k][0], stones[k][1]if buttonDists[i][sx][sy] ! -1 buttonDists[j][sx][sy] ! -1 {d : buttonDists[i][sx][sy] buttonDists[j][sx][sy]if minDist -1 || d minDist {minDist d}}}dist[i][j] minDistdist[j][i] minDist}}// 如果有机关无法从起点到达或无法到达终点返回 -1for i : 0; i numB; i {if dist[i][numB] -1 || dist[i][numB1] -1 {return -1}}// 状态压缩 DP// dp[mask][i] 当前处于第 i 个机关已触发机关状态为 mask 的最短步数// mask 的第 j 位为 1 表示第 j 个机关已触发INF : math.MaxInt32dp : make([][]int, 1numB)for i : range dp {dp[i] make([]int, numB)for j : range dp[i] {dp[i][j] INF}}// 初始化从起点 S 到每个机关for i : 0; i numB; i {dp[1i][i] dist[i][numB]}// DP 转移for mask : 1; mask (1 numB); mask {for i : 0; i numB; i {if mask(1i) 0 {continue}if dp[mask][i] INF {continue}for j : 0; j numB; j {if mask(1j) ! 0 {continue}if dist[i][j] -1 {continue}nextMask : mask | (1 j)newDist : dp[mask][i] dist[i][j]if newDist dp[nextMask][j] {dp[nextMask][j] newDist}}}}// 所有机关触发后从最后一个机关走到终点 TfinalMask : (1 numB) - 1ans : INFfor i : 0; i numB; i {if dp[finalMask][i] INF || dist[i][numB1] -1 {continue}total : dp[finalMask][i] dist[i][numB1]if total ans {ans total}}if ans INF {return -1}return ans}核心思路步骤 说明BFS 预处理 从 S 和每个 M 分别做 BFS求到全图的最短距离关键点距离计算 枚举石堆 O计算 S→O→M、Mi→O→Mj、M→T 的最短距离状态压缩 DP dp[mask][i] 表示已触发 mask 状态的机关当前在机关 i 的最小步数Go 实现要点- BFS 队列使用切片 [][2]int 模拟队列通过索引 head 实现 O(1) 出队- 多维数组使用 [][][]int 存储每个机关的 BFS 距离矩阵- 状态压缩mask 用 int 表示1numB 作为 DP 数组大小- 无穷大使用 math.MaxInt32 作为 INF复杂度分析- 时间复杂度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)下载文件: [LCP 13 寻宝 Go 实现](sandbox:///mnt/agents/output/lcp13_xun_bao.go)