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

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

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

作者 | 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 = {00, -11};
private int[] dirY = {-1100};

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, 00);
                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;
}


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

有热门推荐?


1.程序员全球最厉害的 14 位程序员

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

3.【算法动画:七分钟理解什么是KMP算法

4.【数据结构十大经典排序算法动画与解析,看我就够了!


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