获取所有钥匙的最短路径

*我们可以建立一个三维组来存储当前的状态，x,y表示所处位置,key表示钥匙状态，对于现在的我来说对下面代码的<<,&,|=符号不是很熟悉，但这些是解决这题的关键。key是用二进制来表示，最开始的值为0，假设有6位二进制数，出现了某个钥匙，我们可以将相对的某个点取为1，1就代表这把钥匙是否出现。因为某个位置最多有k次的走法，所以进行广搜，到遍历的钥匙=总钥匙数就返回值

    // 定义节点结构体，包含坐标和当前持有的钥匙状态  
    struct node {  
        int x, y, key; // x,y表示坐标，key表示当前持有的钥匙状态（二进制表示）  
    };   
    const int N = 34; 
    const int K = 6;    
    const int dirs[4][2] ={{1,0},{-1,0},{0,1},{0,-1}};
    // 访问标记数组，用于记录是否访问过某个状态（坐标+钥匙状态）  
    bool vis[N][N][1 << K] = {0};  
    int sum = 0;       // 记录初始时地图上所有钥匙的集合  
    int n = a.size();  
    int m = a[0].size(); 
    queue<node> q;    
    for (int i = 0; i < n; i++) {  
        for (int j = 0; j < m; j++) {  
            if (a[i][j] == '@') { // 起点  
                q.push({i, j, 0}); // 加入队列，初始时没有钥匙  
            }  
            if (a[i][j] >= 'a' && a[i][j] <= 'f') { // 遍历所有钥匙，记录初始钥匙状态  
                sum|= 1 << (a[i][j] - 'a');  
            }  
        }  
    }  
      
    int lever = 0; // 记录当前搜索的层级（用于计算路径长度）  
    while (!q.empty()) {  
        int size = q.size(); // 当前层级的节点数  
        for (int i = 0; i < size; i++) {  
            auto [x, y, key] = q.front(); // 取出当前节点  
            q.pop();  
              
            // 遍历四个方向  
            for (int d = 0; d < 4; d++) {  
                int dx = x + dirs[d][0];  
                int dy = y + dirs[d][1];  
                  
                // 检查是否越界  
                if (dx < 0 || dx >= n || dy < 0 || dy >= m) {  
                    continue;  
                }  
                  
                char cell = a[dx][dy]; // 当前位置的字符  
                int ds = key; // 当前位置的状态（钥匙状态）  
                  
                // 如果是墙，则跳过  
                if (cell == '#') {  
                    continue;  
                }  
                  
                // 如果是门，且没有对应的钥匙，则跳过  
                if (cell >= 'A' && cell <= 'F') {  
                    if ((ds & (1 << (cell - 'A'))) == 0) {  
                        continue;  
                    }  
                }  
                // 如果是钥匙，则更新状态  
                if (cell >= 'a' && cell <= 'f') {  
                    ds |= (1 << (cell - 'a'));  
                }  
                  
                // 如果已经收集了所有钥匙，则返回当前层级+1作为最短路径长度  
                if (ds == sum) {  
                    return lever + 1;  
                }  
                  
                // 如果当前状态未被访问过，则标记并加入队列  
                if (!vis[dx][dy][ds]) {  
                    vis[dx][dy][ds] = 1;  
                    q.push({dx, dy, ds});  
                }  
            }  
        }  
        lever++; // 完成当前层级的搜索，层级+1  
    }  
      
    // 如果无法收集所有钥匙并到达终点，则返回-1  
    return -1;  
}