今天分享的题目来源于 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
. . . .
对于图上的遍历，不管是使用深度优先搜索，还是使用广度优先搜索，我们都会使用一个数据结构用来记录我们走过的点，根据具体的要求，这个数据结构可以是数组，也可以是 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 queue = new LinkedList<>();
Set visited = new HashSet<>();
int totalKeysNum = 0;
for (int i = 0; i for (int j = 0; 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()) {
