题目描述

给定一个二维网格 grid。"." 代表一个空房间，"#" 代表一堵墙，"@" 是起点，（"a", "b", …）代表钥匙，（"A", "B", …）代表锁。

我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。

假设 K 为钥匙/锁的个数，且满足 1 <= K <= 6，字母表中的前 K 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。

返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。

样例

输入：["@.a.#","###.#","b.A.B"]
输出：8

输入：["@..aA","..B#.","....b"]
输出：6

注意

• 1 <= grid.length <= 30
• 1 <= grid[0].length <= 30
• grid[i][j] 只含有 '.', '#', '@', 'a'-'f' 以及 'A'-'F'。
• 钥匙的数目范围是 ·[1, 6]·，每个钥匙都对应一个不同的字母，正好打开一个对应的锁。

算法

(宽度优先搜索，BFS) $O(nm2^K)$

1. 我们在普通 BFS 的基础上，将状态再扩充一维，表示当前已经取得的钥匙集合，用二进制表示。所以，现在的状态为三元组 (x, y, keys)。
2. 接下来按照普通 BFS 进行扩展即可，起点的状态为 (sx, sy, 0)，距离为 0，其余为正无穷。遇到墙或者到达没有钥匙的门都是非法转移。

时间复杂度

• 每个状态仅遍历一次，故总时间复杂度为 $O(nm2^K)$。

C++ 代码

struct S {
    int x, y, keys;
    S(int x_, int y_, int keys_) : x(x_), y(y_), keys(keys_) {}
};

class Solution {
public:
    int shortestPathAllKeys(vector<string>& grid) {
        int n = grid.size(), m = grid[0].size();
        int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
        int K = 0;
        queue<S> q;
        vector<vector<vector<int>>> dis(n, vector<vector<int>>(m, vector<int>(1 << 6, 1000000)));

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '@') {
                    q.push(S(i, j, 0));
                    dis[i][j][0] = 0;
                }
                else if (grid[i][j] >= 'a' && grid[i][j] <= 'f')
                    K++;
            }

        while (!q.empty()) {
            S sta = q.front();
            q.pop();
            for (int i = 0; i < 4; i++) {
                int x = sta.x + dx[i], y = sta.y + dy[i];
                if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == '#')
                    continue;

                if (grid[x][y] >= 'A' && grid[x][y] <= 'F'
                    && !(sta.keys & (1 << (grid[x][y] - 'A'))))
                    continue;

                int nxtkeys = sta.keys;
                if (grid[x][y] >= 'a' && grid[x][y] <= 'f')
                    nxtkeys |= 1 << (grid[x][y] - 'a');

                S nxt(x, y, nxtkeys);

                if (dis[x][y][nxtkeys] > dis[sta.x][sta.y][sta.keys] + 1) {
                    dis[x][y][nxtkeys] = dis[sta.x][sta.y][sta.keys] + 1;
                    q.push(nxt);
                }
            }
        }
        int ans = 1000000;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (ans > dis[i][j][(1 << K) - 1])
                    ans = dis[i][j][(1 << K) - 1];

        if (ans == 1000000)
            ans = -1;

        return ans;
    }
};