[LeetCode] 864. Shortest Path to Get All Keys

[grandyang]

We are given a 2-dimensional grid. "." is an empty cell, "#" is a wall, "@" is the starting point, ("a", "b", ...) are keys, and ("A", "B", ...) are locks.

We start at the starting point, and one move consists of walking one space in one of the 4 cardinal directions.  We cannot walk outside the grid, or walk into a wall.  If we walk over a key, we pick it up.  We can't walk over a lock unless we have the corresponding key.

For some 1 <= K <= 6, there is exactly one lowercase and one uppercase letter of the first Kletters of the English alphabet in the grid.  This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.

Return the lowest number of moves to acquire all keys.  If it's impossible, return -1.

Example 1:

Input: ["@.a.#","###.#","b.A.B"]
Output: 8

Example 2:

Input: ["@..aA","..B#.","....b"]
Output: 6

Note:

1. 1 <= grid.length <= 30
2. 1 <= grid[0].length <= 30
3. grid[i][j] contains only '.', '#', '@', 'a'-``'f``' and 'A'-'F'
4. The number of keys is in [1, 6].  Each key has a different letter and opens exactly one lock.

这道题给了我们一个迷宫，其中的点表示可通过的位置，井号表示墙，不能通过。小写字母表示钥匙，大写字母表示门，只有拿到了对应的钥匙才能通过门的地方，有点红白机游戏的感觉。问我们收集到所有的钥匙需要的最小步数，当无法收到所有钥匙的时候，返回 -1。对于迷宫遍历找最小步数的题，应该并不陌生，基本都是用 BFS 来解的。这里虽然没有一个固定的终点位置，但也是有终止条件的，那就是收集到所有的钥匙。这道题好就好在对钥匙进行了一些限定，最多有6把，最少有1把，而且都是按字母顺序出现的，就是说只有一把钥匙的时候，一定是a，两把的话一定是a和b。我们需要保存所有当前已经获得的钥匙，并且还要随时查询是否已经获得了某个特定的钥匙，还需要查询是否已经获得了所有的钥匙。由于之前说了知道了钥匙的个数，就能确定是哪些钥匙，这样就可以对钥匙进行编号，钥匙a编为0，同理，b，c，d，e，f 分别编为 1，2，3，4，5。最简单的实现就是用一个长度为k的 boolean 数组，获得了某个钥匙就标记为 true，查询某个钥匙是否存在就直接在数组中对应位置查询即可，判断是否获得所有钥匙就线性遍历一下数组即可，由于最多就6把钥匙，所以遍历也很快。当然，若我们想秀一波技巧，也可以将钥匙编码成二进制数，对应位上的0和1表示该钥匙是存在，比如二进制数 111111 就表示六把钥匙都有了，而 100111 就表示有钥匙 a，d，e 和f，这样查询某个钥匙或查询所有钥匙的时间复杂度都是常数级了，既省了空间又省了时间，岂不美哉？！

分析到这里，基本上难点都 cover 了，可以准备写代码了。整体框架还是经典的 BFS 写法，再稍加改动即可。这里的队列 queue 不能只放位置信息，还需要放当前的钥匙信息，因为到达不同的位置获得的钥匙个数可能是不同的，二维的位置信息编码成一个整数，再加上钥匙的整数，组成一个 pair 对儿放到队列中。由于参数中没有事先告诉我们起点的位置，所以需要先遍历一遍整个迷宫，找到@符号，将位置和当前钥匙信息加入到 queue 中。为了避免死循环，BFS 遍历是需要记录已经访问过的位置的，这里的状态当然也要加入当前钥匙的信息，为了简单起见，将其编码成一个字符串，前半部分放位置编码成的整数，中间加个下划线，后面放钥匙信息的整数，组成的字符串放到 HashSet 中即可。遍历的过程中同时还要统计钥匙的个数，有了总个数 keyCnt，就能知道拿到所有钥匙后编码成的整数。在 while 循环，采用层序遍历的机制，对于同一层的结点，分别取出位置信息和钥匙信息，此时先判断下是否已经拿到所有钥匙了，是的话直接返回当前步数 res。否则就要检测其四个相邻位置，需要注意的是，对于每个相邻位置，一定要重新取出之前的钥匙信息，否则一旦钥匙信息修改了而没有重置的话，直接到同一层的其他结点可能会引起错误。取出的邻居结点的位置要先判断是否越界，还要判断是否为墙，是的话就直接跳过。若是门的话，要看当前是否有该门对应的钥匙，有的话才能通过。若遇到了钥匙，则需要修改钥匙信息。这些都完成了之后，将当前的位置和钥匙信息编码成一个字符串，看 HashSet 是否已经有了这个状态，没有的话，则加入 HashSet，并同时加入 queue，每当一层结点遍历完成后，结果 res 自增1即可，参见代码如下：

class Solution {
public:
    int shortestPathAllKeys(vector<string>& grid) {
        int m = grid.size(), n = grid[0].size(), keyCnt = 0, res = 0;
        queue<pair<int, int>> q;
        unordered_set<string> visited;
        vector<int> dirX{-1, 0, 1, 0}, dirY{0, 1, 0, -1};
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '@') {
                    q.push({i * n + j, 0});
                    visited.insert(to_string(i * n + j) + "_0");
                }
                if (grid[i][j] >= 'a' && grid[i][j] <= 'f') ++keyCnt;
            }
        }
        while (!q.empty()) {
            for (int i = q.size(); i > 0; --i) {
                int t = q.front().first, curKeys = q.front().second; q.pop();
                if (curKeys == (1 << keyCnt) - 1) return res;
                for (int k = 0; k < 4; ++k) {
                    int x = t / n + dirX[k], y = t % n + dirY[k], keys = curKeys;
                    if (x < 0 || x >= m || y < 0 || y >= n) continue;
                    char c = grid[x][y];
                    if (c == '#') continue;
                    if (c >= 'A' && c <= 'F' && ((keys >> (c - 'A')) & 1) == 0) continue;
                    if (c >= 'a' && c <= 'f') keys |= 1 << (c - 'a');
                    string str = to_string(x * n + y) + "_" + to_string(keys);
                    if (!visited.count(str)) {
                        visited.insert(str);
                        q.push({x * n + y, keys});
                    }
                }
            }
            ++res;
        }
        return -1;
    }
};

Github 同步地址:

#864

参考资料：

https://leetcode.com/problems/shortest-path-to-get-all-keys/

https://leetcode.com/problems/shortest-path-to-get-all-keys/discuss/146878/Java-BFS-Solution

https://leetcode.com/problems/shortest-path-to-get-all-keys/discuss/146941/C%2B%2B-BFS-with-current-key-recorded-visited-map-(12ms)

LeetCode All in One 题目讲解汇总(持续更新中...)