力扣(LeetCode)864. 获取所有钥匙的最短路径(C++)

bfs+状态压缩

本题是走迷宫类型问题，求起点到终态的最短路。走迷宫和 $bfs$ 思想是一致的，因为 $bfs$ 每次对当前所有状态整体外扩一格，它第一次走到终态，经过的路程一定是最短路。

确定使用 $bfs$ ，它的起点就是 ${}^{\prime }{@}^{\prime }$ 所在的坐标，终态是集齐所有钥匙。如何表示终态？可以用状态压缩，让矩阵显示当前持有的钥匙。用每个二进制位代表一把钥匙。二进制位是 $1$ ，表示有这把钥匙， $0$ 表示没有这把钥匙。
例如：一共 $4$ 把钥匙，" $1001$ " 表示，当前有第 $3$ 把，第 $0$ 把钥匙，但是没有 $2、1$ 钥匙。

代码展示

class Solution {
public:
    int shortestPathAllKeys(vector<string>& grid) {
        int dx[4] = {-1,0,1,0};//上右下左
        int dy[4] = {0,1,0,-1};
        int m = grid.size(),n = grid[0].size();//m行n列
        int sx = 0,sy =0;//起始地点
        int cnt = 0;//统计小写字母(钥匙)数量
        for(int i =0;i<m;i++)
            for(int j = 0;j<n;j++)
                if('@'==grid[i][j]) sx = i,sy = j;
                else if(islower(grid[i][j])) cnt++; 
        queue<tuple<int,int,int>> q({{{sx,sy,0}}});///插入三元组 x,y,k(钥匙)
        vector<vector<vector<int>>> dis(m,vector<vector<int>>(n,vector<int>(1<<cnt,-1)));
        dis[sx][sy][0] = 0;//初始状态距离为0;
        while(q.size()){//队列非空
            auto [x,y,k] = q.front();//保存队首坐标,钥匙编码
            q.pop();
            for(int i =0;i<4;i++){
                int a = x + dx[i],b = y+dy[i];//移动
                if(a>=0&&b>=0&&a<m&&b<n&&'#'!=grid[a][b]){//边界保护
                    char c = grid[a][b];//暂存字符
                    if(islower(c)){
                        int t = k;//暂存k
                        t |= 1<<(c-'a');//加入新的钥匙
                        if(t==(1<<cnt) - 1) return dis[x][y][k]+1;//第一转移到全部钥匙的状态//返回答案
                        if(-1 == dis[a][b][t]){//新状态没有搜索过。
                            dis[a][b][t] = dis[x][y][k] + 1;
                            // if(t==(1<
                            q.emplace(a,b,t);
                        }
                    }else{//起点,空房间 || isupper(grid[a][b])
                        if((('.'==c||'@'==c)||(k>>(c-'A'))&1)&&-1==dis[a][b][k]){锁对应的钥匙存在
                            dis[a][b][k] = dis[x][y][k] + 1;
                            q.emplace(a,b,k);
                        }
                    }
                }
            }
        }
        return -1;//无法获取所有钥匙
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC

复杂度分析

1. 时间复杂度: $O(m\times n\times 2^k)$， $m$ 是行数， $n$ 是列数， $k$ 是钥匙个数。最坏要遍历所有状态，时间复杂度 $O(m\times n\times 2^k)$ 。
2. 空间复杂度: $O(m\times n\times 2^k)$。$dis$ 的空间复杂度和 $q$ 的最坏空间复杂度都是 $O(m\times n\times 2^k)$。