Shortest Path to Get All Keys
Problem
You are given a grid with walls '#', empty '.', start '@', lowercase keys, and uppercase locks. Return the fewest moves to collect every key; you can only walk through a lock if you have its key.
grid = ["@.a.#","###.#","b.A.B"]8from collections import deque
def shortestPathAllKeys(grid):
R, C = len(grid), len(grid[0])
sr = sc = 0; full = 0
for r in range(R):
for c in range(C):
ch = grid[r][c]
if ch == '@': sr, sc = r, c
elif 'a' <= ch <= 'f': full |= 1 << (ord(ch) - ord('a'))
q = deque([(sr, sc, 0, 0)])
seen = {(sr, sc, 0)}
while q:
r, c, mask, d = q.popleft()
if mask == full: return d
for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
nr, nc = r + dr, c + dc
if not (0 <= nr < R and 0 <= nc < C): continue
ch = grid[nr][nc]
if ch == '#': continue
nm = mask
if 'a' <= ch <= 'f': nm |= 1 << (ord(ch) - ord('a'))
if 'A' <= ch <= 'F' and not (mask >> (ord(ch) - ord('A'))) & 1: continue
if (nr, nc, nm) in seen: continue
seen.add((nr, nc, nm))
q.append((nr, nc, nm, d + 1))
return -1function shortestPathAllKeys(grid) {
const R = grid.length, C = grid[0].length;
let sr = 0, sc = 0, full = 0;
for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) {
const ch = grid[r][c];
if (ch === '@') { sr = r; sc = c; }
else if (ch >= 'a' && ch <= 'f') full |= 1 << (ch.charCodeAt(0) - 97);
}
const seen = new Set([sr + ',' + sc + ',0']);
const q = [[sr, sc, 0, 0]]; let head = 0;
while (head < q.length) {
const [r, c, mask, d] = q[head++];
if (mask === full) return d;
for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
const ch = grid[nr][nc];
if (ch === '#') continue;
let nm = mask;
if (ch >= 'a' && ch <= 'f') nm |= 1 << (ch.charCodeAt(0) - 97);
if (ch >= 'A' && ch <= 'F' && !((mask >> (ch.charCodeAt(0) - 65)) & 1)) continue;
const key = nr + ',' + nc + ',' + nm;
if (seen.has(key)) continue;
seen.add(key);
q.push([nr, nc, nm, d + 1]);
}
}
return -1;
}class Solution {
public int shortestPathAllKeys(String[] grid) {
int R = grid.length, C = grid[0].length(), sr = 0, sc = 0, full = 0;
for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) {
char ch = grid[r].charAt(c);
if (ch == '@') { sr = r; sc = c; }
else if (ch >= 'a' && ch <= 'f') full |= 1 << (ch - 'a');
}
boolean[][][] seen = new boolean[R][C][64];
seen[sr][sc][0] = true;
Deque<int[]> q = new ArrayDeque<>();
q.offer(new int[]{ sr, sc, 0, 0 });
int[][] D = { {1,0},{-1,0},{0,1},{0,-1} };
while (!q.isEmpty()) {
int[] cur = q.poll();
int r = cur[0], c = cur[1], mask = cur[2], d = cur[3];
if (mask == full) return d;
for (int[] dd : D) {
int nr = r + dd[0], nc = c + dd[1];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
char ch = grid[nr].charAt(nc);
if (ch == '#') continue;
int nm = mask;
if (ch >= 'a' && ch <= 'f') nm |= 1 << (ch - 'a');
if (ch >= 'A' && ch <= 'F' && ((mask >> (ch - 'A')) & 1) == 0) continue;
if (seen[nr][nc][nm]) continue;
seen[nr][nc][nm] = true;
q.offer(new int[]{ nr, nc, nm, d + 1 });
}
}
return -1;
}
}int shortestPathAllKeys(vector<string>& grid) {
int R = (int)grid.size(), C = (int)grid[0].size(), sr = 0, sc = 0, full = 0;
for (int r = 0; r < R; r++) for (int c = 0; c < C; c++) {
char ch = grid[r][c];
if (ch == '@') { sr = r; sc = c; }
else if (ch >= 'a' && ch <= 'f') full |= 1 << (ch - 'a');
}
vector<vector<vector<bool>>> seen(R, vector<vector<bool>>(C, vector<bool>(64, false)));
seen[sr][sc][0] = true;
queue<tuple<int, int, int, int>> q;
q.push({sr, sc, 0, 0});
int D[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
while (!q.empty()) {
auto [r, c, mask, d] = q.front(); q.pop();
if (mask == full) return d;
for (auto& dd : D) {
int nr = r + dd[0], nc = c + dd[1];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
char ch = grid[nr][nc];
if (ch == '#') continue;
int nm = mask;
if (ch >= 'a' && ch <= 'f') nm |= 1 << (ch - 'a');
if (ch >= 'A' && ch <= 'F' && !((mask >> (ch - 'A')) & 1)) continue;
if (seen[nr][nc][nm]) continue;
seen[nr][nc][nm] = true;
q.push({nr, nc, nm, d + 1});
}
}
return -1;
}Explanation
We want the fewest moves to collect every key, which means BFS for shortest distance. But your position alone isn't enough — which keys you're holding changes where you can walk. So the BFS state is (row, col, keys), and we pack the set of keys into a bitmask.
Each key letter a..f gets a bit: holding key a sets bit 0, key c sets bit 2, and so on. We precompute full as the mask with one bit per key in the grid — reaching it means we've collected them all.
From each state we try the four neighbors. Walls # are blocked. Stepping on a key letter ORs its bit into the mask nm. Stepping on a lock A..F is only allowed if we already hold the matching key (its bit is set in mask), otherwise we skip it.
We mark visited states by the full triple (r, c, mask), not just position — the same square is worth revisiting if we now carry more keys. The first time a popped state has mask == full, its distance is the answer.
Example: ["@.a.#","###.#","b.A.B"]. The BFS grabs key a, routes down to key b (passing lock A only after holding a), and the shortest such tour takes 8 moves.