获取所有钥匙的最短路径

class Solution {  
public:  
struct node {  
    int x, y; // 位置  
    int keys; // 钥匙状态（位掩码）  
};  
    int shortestPathAllKeys(vector<string>& grid) {  
        int k = 6;  
        int n = grid.size(), m = grid[0].length();  
        int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};//遍历我的上下左右 
        bool vis[105][105][1 << k];  // 访问标记，记录是否访问过某个位置和钥匙状态 
   //1<<k什么意思？ 相当于2的k次方 相当于我再二进制中一直左移直到k次比如6次就是100000（二进制）
        memset(vis, 0, sizeof(vis));  // 初始化起点和收集所有钥匙的位掩码  
  
        int startX, startY, allKeys = 0;//开始的位置和总钥匙数量  
        queue<node> q; // 使用自定义结构体 node 
  
        // 初始化起点和收集所有钥匙的位掩码  
        for (int i = 0; i < n; ++i) {  
            for (int j = 0; j < m; ++j) {  
                if (grid[i][j] == '@') {//找到开始的位置并记录 
                    startX = i;  
                    startY = j;  
                }  
                if (grid[i][j] >= 'a' && grid[i][j] <= 'f') {  
                    allKeys |= 1 << (grid[i][j] - 'a');//记录初始的钥匙数量
                }  
            }  
        }  
  
        q.push(State(startX, startY, 0)); // 初始位置，钥匙状态为0  
        vis[startX][startY][0] = 1;//开始位置进行记录  
  
        int steps = 0; //记录我最少走了几步
        while (!q.empty()) {  
            int size = q.size();  
            for (int i = 0; i < size; ++i) {  
                State curr = q.front();//将我的坐标进行输出 
                q.pop();  
  
                if (curr.keys == allKeys) return steps; // 所有钥匙都找到了  
  
                for (int j = 0; j < 4; ++j) {//遍历这个点的上下左右位置 
                    int nx = curr.x + dir[j][0];  
                    int ny = curr.y + dir[j][1];  
  
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;//超出我棋盘范围就删
                    char c = grid[nx][ny];  
  
                    if (c == '#') continue; // 障碍物  
  
                    int nextKeys = curr.keys;  
                    if (c >= 'a' && c <= 'f') { //为什么这样子捡钥匙？这样子可以判断我捡的是哪吧
                //例如abcd四把钥匙捡到c这样子我记录的位置就是0100捡到钥匙的地方我记成1  
                        nextKeys |= 1 << (c - 'a'); // 捡起钥匙  
                    }  
  
                    if (c >= 'A' && c <= 'F' && !(curr.keys & (1 << (c - 'A')))) {  
                        continue; // 如果没有相应的钥匙，则不能通过  
                    }  
  
                    if (!vis[nx][ny][nextKeys]) {  
                        vis[nx][ny][nextKeys] = true;//现在到这个地方我走过了并且我有几个钥匙 
                        q.push(State(nx, ny, nextKeys));  
                    }  
                }  
            }  
            ++steps;/走过了这一步走下一步  
        }  
  
        return -1; // 没有找到所有钥匙  
    }  
};