Leetcode#864 Shortest Path to Ge

题目大意

给定一个二维的平面迷宫，其中@表示出发点，.表示平地可正常通行，#表示墙壁不可通行。 A-F表示锁，需要获取到对应钥匙(小写字母)之后才能通行。 a-f表示钥匙🔑对应大写字母的锁。 问从出发点开始以最少多少步可以拿到迷宫中的所有钥匙？如果不可能的话，返回-1

• 其中，锁和钥匙是配对出现的

样例：

@...a
.###A
b.BCc

期望结果为： 10

解题思路

迷宫遍历 + 最少步数 = BFS
注意 状态的表示即可，这里我使用了三维数组表示状态(x坐标，y坐标，身上携带的钥匙串)
内存开销是 地图大小*钥匙串 = 31 * 31 * (1<<6) a-f 6把钥匙

☝️一个技巧：使用 位运算 异或判断 身上钥匙串是否有对应的钥匙，比较方便

//35 / 35 test cases passed.
//Status: Accepted
//Runtime: 12 ms

static auto _ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    return 0;
}();

typedef pair<int, int> point;
class State{
public:
    int step,keys;
    point p;
    State(int _s,int _keys,point _p){
        step = _s;
        keys = _keys;
        p = _p;
    }
};

class Solution {
public:
    int shortestPathAllKeys(vector<string>& grid) {
        
        queue<State> road;
        unsigned totalKeyCount = 0;
        
        int n = (int)grid.size();
        int m = (int)grid[0].size();
        
        for(size_t i = 0; i<n; ++i){
            for(size_t j = 0;j<m; ++j){
                if(grid[i][j] == '@'){
                    road.push(State(0, 0, make_pair(i, j)));
                }
                if(grid[i][j] >= 'a' && grid[i][j] <= 'f'){
                    ++totalKeyCount;
                }
            }
        }
        
        const int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
        vector<vector<vector<int>>> vis{31,vector<vector<int>>{31,vector<int>(64,31*31)}};
        vis[road.front().p.first][road.front().p.second][road.front().keys] = 0;
        while(!road.empty()){
            State now = road.front();
            road.pop();
            
            if(now.keys == (1<<totalKeyCount) - 1){
                return now.step;
            }
            
            for(int i = 0; i<4; ++i){
                int xx = now.p.first + dir[i][0];
                int yy = now.p.second + dir[i][1];
                
                if(xx<0 || xx>=n || yy<0 || yy>=m) continue;
                if(grid[xx][yy] == '#') continue;
                
                
                if(grid[xx][yy] >= 'A' && grid[xx][yy] <= 'F'){
                    int lock = 1 << (grid[xx][yy] - 'A');
                    // 身上的钥匙串🔑 打不开锁！
                    if(!(now.keys&lock)){
                        continue;
                    }
                }
                
                State next(now.step +1,now.keys,make_pair(xx, yy));
                if(grid[xx][yy]>='a' && grid[xx][yy]<='f'){
                    int tmpKey = 1 << (grid[xx][yy] - 'a');
                    // 获得钥匙一把，刷新钥匙串🔑
                    next.keys = next.keys | tmpKey;
                }
                
                if(next.step < vis[next.p.first][next.p.second][next.keys]){
                    vis[next.p.first][next.p.second][next.keys] = next.step;
                    road.push(next);
                }
            }
        }
        return -1;
    }
};