使用位运算处理一道难题：获取所有钥匙的最短路径

古城微笑少年丶 2024-04-18 22:48 49阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

作者 | P.yh

来源 | 五分钟学算法

今天分享的题目来源于 LeetCode 第 864 号问题：获取所有钥匙的最短路径。题目难度为 Hard，如果不借助 **位运算** 来处理，那它的解法相当繁琐，甚至需要使用 **Dijkstra** 。

### 题目描述 ###

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

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

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

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

**示例 1：**

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

**示例 2：**

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

**提示：**

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

### 题目解析 ###

非常有意思的一道搜索问题，在一个矩阵内，给定初始点，要你取得图中所有的钥匙，并输出取得所有钥匙所需要的 **最小步数**，门只有对应的钥匙才能开，另外图中还会有墙阻断路线。

看到最小步数，脑袋里面马上反应是使用 **广度优先搜索**。

其实我们可以把矩阵看成是一个图，矩阵中的对应的位置就是图上的节点，每个位置和其上下左右四个位置相连，这样图上的边也就有了。

难点在于细节的把控上面，还有就是你怎么解决 “**对应钥匙开对应门**”，我们来看看下面这个例子:

. . . . . . . . . . B
    . . . . # . . . . . .
    . @ . A b # . . . . a
    . . . . # . . . . . .

对于图上的遍历，不管是使用深度优先搜索，还是使用广度优先搜索，我们都会使用一个数据结构用来记录我们走过的点，根据具体的要求，这个数据结构可以是数组，也可以是 Set，目的是防止走之前的老路，如果没有这样一个数据结构，程序会无休止地运行下去。

但是你看到上面的例子，我们必须去到远处拿到钥匙 a 之后，我们才可以拿钥匙 b，你会发现如果要遵循 “访问过的节点不能再继续访问” 这么一个要求，那么我们的实现思路在这里会遇到阻碍。

一开始，遇到这个问题，我使用了一些数据结构去记录门还有点和点的距离，最后发现设计太复杂，程序没法写下去了。

看到 discuss 里面有一个思路非常好，**我们判断一个点是不是被访问过，不仅仅看其二维坐标，还要看第三维的东西，这里的第三维的东西就是钥匙**，如果我们之前到一个位置上面只拿了两把钥匙，这时我们手里有三把钥匙，那么我们依然可以到这个位置上面去，钥匙在这里就好像是第三维的坐标一样。

因为题目里面说到最多只会出现 6 把钥匙，对于每把钥匙只有两种状态，获得和没有获得，这里还有一个技巧就是用一个整数去表示当前我们获得的钥匙，再次体会到了位运算的强大之处，**发现如果一类东西的可能的个数并不是特别大，并且每个东西只有两种状态的时候，可以考虑使用整形去表示，并用位运算进行处理**。

### 实现代码 ###

private class Pair {
        int x, y, steps, keys;
        Pair(int x, int y, int steps, int keys) {
            this.x = x;
            this.y = y;
            this.steps = steps;
            this.keys = keys;
        }
    
        @Override
        public boolean equals(Object obj) {
            Pair o = (Pair)obj;
            if (this == o) {
                return true;
            }
    
            return (this.x == o.x && this.y == o.y && this.keys == o.keys);
        }
    
        @Override
        public int hashCode () {
            return x * 100 + y * 10 + keys;
        }
    }
    
    private int[] dirX = {0, 0, -1, 1};
    private int[] dirY = {-1, 1, 0, 0};
    
    public int shortestPathAllKeys(String[] grid) {
        if (grid == null || grid.length == 0 || grid[0].equals("")) {
            return -1;
        }
    
        int m = grid.length, n = grid[0].length();
    
        Queue<Pair> queue = new LinkedList<>();
    
        Set<Pair> visited = new HashSet<>();
    
        int totalKeysNum = 0;
    
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                char cur = grid[i].charAt(j);
                if (cur >= 'a' && cur <= 'f') {
                    totalKeysNum++;
                }
    
                if (cur == '@') {
                    Pair startPoint = new Pair(i, j, 0, 0);
                    queue.offer(startPoint);
                    visited.add(startPoint);
                }
            }
        }
    
        while (!queue.isEmpty()) {
            Pair cur = queue.poll();
    
            if (cur.keys == (1 << totalKeysNum) - 1) {
                return cur.steps;
            }
    
            for (int i = 0; i < 4; ++i) {
                int nextX = cur.x + dirX[i];
                int nextY = cur.y + dirY[i];
    
                if (nextX < 0 || nextY < 0 || nextX >= m || nextY >= n) {
                    continue;
                }
    
                char c = grid[nextX].charAt(nextY);
    
                Pair nextInfo = new Pair(nextX, nextY, cur.steps + 1, cur.keys);
    
                if (c == '#' || (c >= 'A' && c <= 'F' && ((cur.keys >> c - 'A') & 1) == 0)) {
                    continue;
                }
    
                if (visited.contains(nextInfo)) {
                    continue;
                }
    
                if (c >= 'a' && c <= 'f') {
                    nextInfo.keys |= (1 << c - 'a');
                }
    
                queue.offer(nextInfo);
                visited.add(nextInfo);
            }
        }
    
        return -1;
    }

![640?][640]

**有热门推荐?**

1.【程序员】[全球最厉害的 14 位程序员][14]

2.【GitHub】[我在 GitHub 上看到了一个丧心病狂的开源项目！][GitHub]

3.【算法】[动画：七分钟理解什么是KMP算法][KMP]

4.【数据结构】[十大经典排序算法动画与解析，看我就够了][Link 1]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

[640_wx_fmt_jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/70b1c70df3e149c085e0cc7555395c52.png
[640]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/f74577a9ab1d4830ad6fdb4d9634e83b.png
[14]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247486099&idx=1&sn=6ea84944fe6a3d6dd1af2b00f3e53002&chksm=fa0e6512cd79ec04c8e8c63e74d78cc23629b88290a8e0642e5e44601f99fc39a3ea530867bc&scene=21#wechat_redirect
[GitHub]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247486254&idx=1&sn=654c208601879fe1b76c682a069a4e6a&chksm=fa0e64afcd79edb960a9863c7af7e6de5893da2326e6eca2bcd9d68061966d200ba0e189ab91&scene=21#wechat_redirect
[KMP]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485939&idx=1&sn=b25f39b5644da92c4047bbbd9936f73c&chksm=fa0e6672cd79ef64dda0a21e23c2817edf4a64cbb75b9bed328d6519c6cd4fef36d03a4cb309&scene=21#wechat_redirect
[Link 1]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[640_wx_fmt_jpeg 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/3f914ec630954225b66ada70622ac526.png