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

`class Solution {public:    int shortestPathAllKeys(vector<string>& grid) {        int m=grid.size(), n=grid[0].size();        queue<int> q;        vector<vector<vector<int>>> state(m,vector<vector<int>>(n,vector<int>(64,0)));        int all_keys=0;        int go[]={-1,0,1,0,-1};​        for(int i=0;i<m;i++)            for(int j=0;j<n;j++){               auto c=grid[i][j];                if(c=='@')                {                    q.push(i<<16 | j<<8);                    state[i][j][0]=1;                }                if(c>='a' && c<='f')                    all_keys |= 1 << (c-'a');            }​        int step=0;        while(!q.empty())        {           int  size=q.size();            while(size--)            {                int s=q.front();                q.pop();                int x=s>>16;                int y = s>>8 & 0xFF;                int keys=s & 0xFF;                if(keys == all_keys)                    return step;                for(int i=0;i<4;i++)                {                    int nx= x+ go[i];                    int ny= y+ go[i+1];​                    if(nx <0 || nx >=m ||ny <0 || ny >=n) continue;                    auto c = grid[nx][ny];                    int nkeys=keys;                    if(c=='#') continue;                    if(c>='A' && c<='F' && !((1<<(c-'A')) & keys) ) continue;                    if(c>='a' && c<='f') nkeys |= 1<<(c-'a');                    if(state[nx][ny][nkeys]) continue;                    q.push((nx <<16) | (ny <<8) | nkeys);                    state[nx][ny][nkeys]=1;                }            }            step++;        }​        return -1;​    }};`