題目大意

給定一個二維的平面迷宮抖单，其中@表示出發(fā)點讳窟，.表示平地可正常通行，#表示墻壁不可通行饲帅。 A-F表示鎖砚偶，需要獲取到對應(yīng)鑰匙(小寫字母)之后才能通行。 a-f表示鑰匙??對應(yīng)大寫字母的鎖洒闸。 問從出發(fā)點開始以最少多少步可以拿到迷宮中的所有鑰匙？如果不可能的話均芽，返回-1

• 其中丘逸，鎖和鑰匙是配對出現(xiàn)的

樣例：

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

期望結(jié)果為： 10

解題思路

迷宮遍歷 + 最少步數(shù) = BFS
注意 狀態(tài)的表示即可，這里我使用了三維數(shù)組表示狀態(tài)(x坐標掀宋，y坐標深纲，身上攜帶的鑰匙串)
內(nèi)存開銷是 地圖大小*鑰匙串 = 31 * 31 * (1<<6) a-f 6把鑰匙

??一個技巧：使用 位運算 異或判斷 身上鑰匙串是否有對應(yīng)的鑰匙，比較方便

//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;
    }
};