题解：
- bfs
- 总共不超过6把钥匙，通过位运算保存钥匙
class Solution {
public int shortestPathAllKeys(String[] grid) {
int[][][] dist = new int[31][31][64];
int n = grid.length, m = grid[0].length(), S = 0;
for (int i = 0; i < n; i++) {
dist[i] = new int[31][];
for (int j = 0; j < m; j++) {
dist[i][j] = new int[64];
for (int k = 0; k < 64; k ++) {
dist[i][j][k] = Integer.MAX_VALUE;
}
}
}
Queue<Node> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 起点
if (grid[i].charAt(j) == '@') {
dist[i][j][0] = 0;
q.offer(new Node(i, j, 0));
} else if (grid[i].charAt(j) >= 'a' && grid[i].charAt(j) <= 'z') {
// 钥匙总数
S++;
}
}
}
int[] dx = new int[]{-1, 0, 1, 0};
int[] dy = new int[]{0, 1, 0, -1};
while (!q.isEmpty()) {
Node t = q.poll();
int d = dist[t.x][t.y][t.s];
// 从这个点出发，向上下左右，四个方向走
for (int i = 0; i < 4; i++) {
int nx = t.x + dx[i], ny = t.y + dy[i], ns = t.s;
// 判断是否合法
if (nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx].charAt(ny) == '#') continue;
char c = grid[nx].charAt(ny);
if (c >= 'a' && c <= 'z') {
ns |= 1 << (c - 'a');
if (dist[nx][ny][ns] > d + 1) {
dist[nx][ny][ns] = d + 1;
// 钥匙凑够了，立马return
if (ns == (1 << S) - 1) return d + 1;
q.offer(new Node(nx, ny, ns));
}
} else if (c >= 'A' && c <= 'Z') {
// 判断此时有没有这个锁的钥匙
int isUnLock = ns & (1 << c - 'A');
if (isUnLock > 0 && dist[nx][ny][ns] > d + 1) {
dist[nx][ny][ns] = d + 1;
q.offer(new Node(nx, ny, ns));
}
} else {
if (dist[nx][ny][ns] > d + 1) {
dist[nx][ny][ns] = d + 1;
q.offer(new Node(nx, ny, ns));
}
}
}
}
return -1;
}
static class Node {
int x, y, s;
public Node(int x, int y, int s) {
this.x = x;
this.y = y;
this.s = s;
}
}
}