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

链接：864.获取所有钥匙的最短路径
难度：Hard
标签：位运算、广度优先搜索、数组、矩阵
简介：返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。

题解 1 - cpp

• 编辑时间：2022-11-10
• 执行用时：16ms
• 内存消耗：9.9MB
• 编程语言：cpp
• 解法介绍：bfs，通过 mask 记录当前拿到的钥匙数。

const int dirs[4][2] = {
    {0, 1}, {0, -1},
    {1, 0}, {-1, 0}
};
struct Node {
    int x, y, mask;
    Node(int x, int y, int mask = 0): x(x), y(y), mask(mask){}
};
class Solution {
public:
    int shortestPathAllKeys(vector<string>& grid) {
        int n = grid.size(), m = grid[0].size(), sx = -1, sy = -1, mmap[35][35][70] = {0}, MAX_MASK = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '@') sx = i, sy = j;
                else if (islower(grid[i][j])) MAX_MASK |= (1 << grid[i][j] - 'a');
            }
        }
        int size = 1, step = 0;
        queue<Node> q;
        q.push(Node(sx, sy));
        mmap[sx][sy][0] = 1;
        while (!q.empty()) {
            Node node = q.front();
            // cout << "===" << endl
            //      << "step = " << step
            //      << ", x = " << node.x
            //      << ", y = " << node.y
            //      << ", mask = " << node.mask
            //      << endl;
            if (node.mask == MAX_MASK) return step;
            q.pop();
            for (int i = 0; i < 4; i++) {
                int nx = node.x + dirs[i][0], ny = node.y + dirs[i][1];
                if (nx < 0 || nx == n || ny < 0 || ny == m) continue;
                char c = grid[nx][ny];
                if (c == '#') continue;
                if (isupper(c) && (node.mask & (1 << c - 'A')) == 0) continue;
                Node next(nx, ny, node.mask);
                if (islower(c)) next.mask |= 1 << c - 'a';
                if (mmap[next.x][next.y][next.mask]) continue;
                mmap[next.x][next.y][next.mask] = 1;
                q.push(next);
            }
            if (--size == 0) {
                size = q.size();
                step++;
            }
        }
        return -1;
    }
};