864. 获取所有钥匙的最短路径.md

864. 获取所有钥匙的最短路径

题目传送门

点击这里

解题思路

最短路径题的标准揭发就是bfs，这里要记录部署，我们可以应用动态规划来表示状态的转移，这道题还需要维持一个钥匙的持有状态来表示能否开锁，用的是状态压缩来表示当前状态，官方解有一个说法很好，如果我们经过某一个位置两次，且两次我们持有的钥匙状况是一致的，那么就是在反复走，走无用的路线，这句话可以细品一下。状态压缩的mask用二进制来表示持有钥匙的情况，然后动态规划数组来更新状态，表示移动的步数，一旦持有了所有钥匙就可以返回。

代码

var dir = [][]int{
    {1, 0},
    {-1, 0},
    {0, 1},
    {0, -1},
}

func shortestPathAllKeys(grid []string) int {
    m, n := len(grid), len(grid[0])
    sx, sy := 0, 0
    key := map[rune]int{}
    for i, r := range grid {
        for j, v := range r {
            if v == '@' { // 起点
                sx, sy = i, j
            } else if unicode.IsLower(v) { 
                if _, ok := key[v]; !ok {
                    key[v] = len(key) // 钥匙
                }
            }
        }
    }
    // (x, y, mask), (x, y) 表示坐标，mask用状态压缩，二进制表示状态，第i位为1则具有该钥匙
    dist := make([][][]int, m)
    for i := range dist {
        dist[i] = make([][]int, n)
        for j := range dist[i] {
            dist[i][j] = make([]int, 1 << len(key))
            for k := range dist[i][j] {
                dist[i][j][k] = -1
            }
        }
    }
    dist[sx][sy][0] = 0 // 起始位置开始
    // bfs遍历路径
    q := [][3]int{{sx, sy, 0}}
    for len(q) > 0 {
        p := q[0]
        q = q[1:]
        x, y, mask := p[0], p[1], p[2]
        for _, v := range dir {
            nx, ny := x+v[0], y+v[1]
            if 0 <= nx && nx < m && 0 <= ny && ny < n && grid[nx][ny] != '#' {
                new := rune(grid[nx][ny])
                if new == '.' || new == '@' {
                    // 如果该状态没有出现过，则可以添加继续搜索
                    if dist[nx][ny][mask] == -1 {
                        dist[nx][ny][mask] = dist[x][y][mask] + 1
                        q = append(q, [3]int{nx, ny, mask})
                    }
                }else if unicode.IsLower(new) {
                    // 如果是钥匙则更新状态
                    t := mask | 1 << key[new]
                    // 同上
                    if dist[nx][ny][t] == -1 {
                        dist[nx][ny][t] = dist[x][y][mask] + 1
                        // 如果获取到了所有钥匙，则直接返回
                        if t == 1 << len(key)-1 {
                            return dist[nx][ny][t]
                        }
                        q = append(q, [3]int{nx, ny, t})
                    }
                }else {
                    // 先去钥匙库里查找是否具有该钥匙，也就是该钥匙的索引
                    idx := key[unicode.ToLower(new)]
                    // 查找当前状态mask是否具有该钥匙，并且当前状态是否未出现过
                    if mask >> idx & 1 > 0 && dist[nx][ny][mask] == -1 {
                        dist[nx][ny][mask] = dist[x][y][mask] + 1
                        q = append(q, [3]int{nx, ny, mask})
                    }
                }
            }
        }
    }
    return -1 
}