题目地址：

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

给定一个二维字符矩阵（题目中给的是字符串数组，实际上可以看成一个二维字符矩阵），里面有且仅有如下字符： 1、一个点.代表空地 2、@代表出发点，出发点也视为空地； 3、小写字母，代表钥匙； 4、大写字母，代表锁； 5、#代表墙，无法通过。 题目保证字母会连续出现（也就是按照abcd的次序出现，不会有出现了a和c但不出现b这样的情况）。一个人从出发点出发，他每一步可以向四周走一步，如果他走到钥匙的位置，则他可以将钥匙存起来；他可以走到锁的位置，只要他有该锁对应的钥匙（“对应”的意思是大小写字母对应，例如钥匙a对应的就是锁A）；他可以走到任意空地上，不能走到墙上。如果要求他搜集到所有的钥匙，问他至少要走多少步。

思路是BFS + 状态压缩。这里要将走到某个位置和身上有哪些钥匙包装成一个状态，然后来做BFS。本质上还是隐式图搜索。例如，从(1, 1)这个位置拥有钥匙a这个状态，如果他走到了(1, 2)并且该位置有b这个钥匙，那么就相当于从隐式图的(1, 1, "a")这个顶点走到了(1, 2, "ab")这个状态。我们把所有的状态建成一个图，那么这个问题相当于在问从(x, y, "")这个状态（(x, y)是出发点坐标）要走到某个搜集完所有钥匙的状态，最短步数是多少，容易想到用BFS来做。对于钥匙，我们可以采用一个32位整数的二进制位来表示哪些钥匙已经拿到了。代码如下：

import java.util.*; public class Solution { class State { int x, y; int keyState; public State(int x, int y, int keyState) { this.x = x; this.y = y; this.keyState = keyState; } @Override public boolean equals(Object o) { State state = (State) o; return x == state.x && y == state.y && keyState == state.keyState; } @Override public int hashCode() { return Objects.hash(x, y, keyState); } } public int shortestPathAllKeys(String[] grid) { // 找一下起始点、钥匙和锁的字母的范围 State start = new State(0, 0, 0); char maxKey = 'a', maxLock = 'A'; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[i].length(); j++) { char ch = grid[i].charAt(j); if (ch == '@') { start.x = i; start.y = j; } else if (ch != '.') { if (Character.isLowerCase(ch)) { maxKey = (char) Math.max(maxKey, ch); } else { maxLock = (char) Math.max(maxLock, ch); } } } } // fullKey代表钥匙拿满的时候所对应的二进制表示 int fullKey = (1 << (maxKey - 'a' + 1)) - 1; // 开始进行BFS Queue<State> queue = new LinkedList<>(); queue.offer(start); Set<State> visited = new HashSet<>(); visited.add(start); int step = 0; while (!queue.isEmpty()) { step++; int size = queue.size(); for (int i = 0; i < size; i++) { State cur = queue.poll(); for (State next : getNexts(cur, grid, visited, maxKey, maxLock)) { // 如果走到的状态钥匙搜集完毕了，则返回步数 if (next.keyState == fullKey) { return step; } visited.add(next); queue.offer(next); } } } return -1; } private List<State> getNexts(State cur, String[] grid, Set<State> visited, char maxKey, char maxLock) { List<State> nexts = new ArrayList<>(); int[] d = {1, 0, -1, 0, 1}; for (int i = 0; i < 4; i++) { int nextX = cur.x + d[i], nextY = cur.y + d[i + 1]; if (inBound(nextX, nextY, grid)) { State next = new State(nextX, nextY, cur.keyState); char ch = grid[nextX].charAt(nextY); // 遇到墙，略过 if (ch == '#') { continue; } // 遇到钥匙，将钥匙拿起来 if ('a' <= ch && ch <= maxKey) { next.keyState |= (1 << (ch - 'a')); } // 遇到锁了，但没有对应的钥匙，略过 if ('A' <= ch && ch <= maxLock && ((cur.keyState >> (ch - 'A')) & 1) != 1) { continue; } // 其余情况就是走到空地了，只要当前状态之前没访问过，就加入nexts列表 if (!visited.contains(next)) { nexts.add(next); } } } return nexts; } private boolean inBound(int x, int y, String[] grid) { return 0 <= x && x < grid.length && 0 <= y && y < grid[0].length(); } }

时空复杂度$O(V+E)$，复杂度本质上要看具体的隐式图的规模。