864. Shortest Path to Get All Keys
Problem Description
You are given an m x n grid grid where:
- '.' is an empty cell.
- '#' is a wall.
- '@' is the starting point.
- Lowercase letters represent keys.
- Uppercase letters represent locks.
You start at the starting point and one move consists of walking one space in one of the four cardinal directions. You cannot walk outside the grid, or walk into a wall.
If you walk over a key, you can pick it up and you cannot walk over a lock unless you have its corresponding key. Return the lowest number of moves to acquire all keys. If it is impossible, return -1.
Examples:
Example 1:
Input: grid = ["@.a.#","###.#","b.A.B"] Output: 8 Explanation: Note that the goal is to obtain all the keys not to open all the locks.
Example 2:
Input: grid = ["@..aA","..B#.","....b"] Output: 6
Example 3:
Input: grid = ["@Aa"] Output: -1
Constraints:
- m == grid.length
- n == grid[i].length
- 1 ≤ m, n ≤ 30
- grid[i][j] is either an empty cell, a wall, the starting point, a key, or a lock.
- The number of keys is in the range [1, 6].
- Each key has a different lowercase letter and its corresponding lock has the same letter in uppercase.
- The starting point '@' appears exactly once in the grid.
Python Solution
class Solution:
def shortestPathAllKeys(self, grid: List[str]) -> int:
m, n = len(grid), len(grid[0])
# Find starting position and count keys
start_x = start_y = key_count = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '@':
start_x, start_y = i, j
elif grid[i][j].islower():
key_count += 1
# State: (x, y, keys)
# keys is a bitmask where the i-th bit represents whether we have the i-th key
queue = deque([(start_x, start_y, 0, 0)]) # (x, y, keys, steps)
seen = {(start_x, start_y, 0)}
while queue:
x, y, keys, steps = queue.popleft()
# Try all four directions
for nx, ny in [(x+1,y), (x-1,y), (x,y+1), (x,y-1)]:
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != '#':
cell = grid[nx][ny]
# If it's a lock and we don't have the key, skip
if cell.isupper() and not (keys & (1 << (ord(cell.lower()) - ord('a')))):
continue
new_keys = keys
# If it's a key, add it to our keyring
if cell.islower():
new_keys |= 1 << (ord(cell) - ord('a'))
if bin(new_keys).count('1') == key_count:
return steps + 1
if (nx, ny, new_keys) not in seen:
seen.add((nx, ny, new_keys))
queue.append((nx, ny, new_keys, steps + 1))
return -1Implementation Notes:
- Uses BFS with state encoding (position + keys collected)
- Time complexity: O(m*n*2^k) where k is number of keys
- Space complexity: O(m*n*2^k)
Java Solution
class Solution {
public int shortestPathAllKeys(String[] grid) {
int m = grid.length, n = grid[0].length();
int startX = 0, startY = 0, keyCount = 0;
// Find starting position and count keys
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
char cell = grid[i].charAt(j);
if (cell == '@') {
startX = i;
startY = j;
} else if (Character.isLowerCase(cell)) {
keyCount++;
}
}
}
// State: (x, y, keys)
Queue queue = new LinkedList<>();
queue.offer(new int[]{startX, startY, 0, 0}); // (x, y, keys, steps)
Set seen = new HashSet<>();
seen.add(startX + "," + startY + ",0");
int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int x = curr[0], y = curr[1], keys = curr[2], steps = curr[3];
for (int[] dir : dirs) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx].charAt(ny) != '#') {
char cell = grid[nx].charAt(ny);
// If it's a lock and we don't have the key, skip
if (Character.isUpperCase(cell) &&
(keys & (1 << (Character.toLowerCase(cell) - 'a'))) == 0) {
continue;
}
int newKeys = keys;
// If it's a key, add it to our keyring
if (Character.isLowerCase(cell)) {
newKeys |= 1 << (cell - 'a');
if (Integer.bitCount(newKeys) == keyCount) {
return steps + 1;
}
}
String state = nx + "," + ny + "," + newKeys;
if (!seen.contains(state)) {
seen.add(state);
queue.offer(new int[]{nx, ny, newKeys, steps + 1});
}
}
}
}
return -1;
}
} C++ Solution
class Solution {
public:
int shortestPathAllKeys(vector& grid) {
int m = grid.size(), n = grid[0].size();
int startX = 0, startY = 0, keyCount = 0;
// Find starting position and count keys
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '@') {
startX = i;
startY = j;
} else if (islower(grid[i][j])) {
keyCount++;
}
}
}
// State: (x, y, keys)
queue> q;
q.push({startX, startY, 0, 0}); // (x, y, keys, steps)
set seen;
seen.insert(to_string(startX) + "," + to_string(startY) + ",0");
vector> dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};
while (!q.empty()) {
auto curr = q.front();
q.pop();
int x = curr[0], y = curr[1], keys = curr[2], steps = curr[3];
for (auto& [dx, dy] : dirs) {
int nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] != '#') {
char cell = grid[nx][ny];
// If it's a lock and we don't have the key, skip
if (isupper(cell) && !(keys & (1 << (tolower(cell) - 'a')))) {
continue;
}
int newKeys = keys;
// If it's a key, add it to our keyring
if (islower(cell)) {
newKeys |= 1 << (cell - 'a');
if (__builtin_popcount(newKeys) == keyCount) {
return steps + 1;
}
}
string state = to_string(nx) + "," + to_string(ny) + "," +
to_string(newKeys);
if (seen.find(state) == seen.end()) {
seen.insert(state);
q.push({nx, ny, newKeys, steps + 1});
}
}
}
}
return -1;
}
}; JavaScript Solution
/**
* @param {string[]} grid
* @return {number}
*/
var shortestPathAllKeys = function(grid) {
const m = grid.length, n = grid[0].length;
let startX = 0, startY = 0, keyCount = 0;
// Find starting position and count keys
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === '@') {
startX = i;
startY = j;
} else if (/[a-z]/.test(grid[i][j])) {
keyCount++;
}
}
}
// State: (x, y, keys)
const queue = [[startX, startY, 0, 0]]; // (x, y, keys, steps)
const seen = new Set([`${startX},${startY},0`]);
const dirs = [[1,0], [-1,0], [0,1], [0,-1]];
while (queue.length) {
const [x, y, keys, steps] = queue.shift();
for (const [dx, dy] of dirs) {
const nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] !== '#') {
const cell = grid[nx][ny];
// If it's a lock and we don't have the key, skip
if (/[A-Z]/.test(cell) &&
!(keys & (1 << (cell.toLowerCase().charCodeAt(0) - 97)))) {
continue;
}
let newKeys = keys;
// If it's a key, add it to our keyring
if (/[a-z]/.test(cell)) {
newKeys |= 1 << (cell.charCodeAt(0) - 97);
if (newKeys.toString(2).split('1').length - 1 === keyCount) {
return steps + 1;
}
}
const state = `${nx},${ny},${newKeys}`;
if (!seen.has(state)) {
seen.add(state);
queue.push([nx, ny, newKeys, steps + 1]);
}
}
}
}
return -1;
};C# Solution
public class Solution {
public int ShortestPathAllKeys(string[] grid) {
int m = grid.Length, n = grid[0].Length;
int startX = 0, startY = 0, keyCount = 0;
// Find starting position and count keys
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '@') {
startX = i;
startY = j;
} else if (char.IsLower(grid[i][j])) {
keyCount++;
}
}
}
// State: (x, y, keys)
var queue = new Queue<(int x, int y, int keys, int steps)>();
queue.Enqueue((startX, startY, 0, 0));
var seen = new HashSet();
seen.Add($"{startX},{startY},0");
var dirs = new (int dx, int dy)[] { (1,0), (-1,0), (0,1), (0,-1) };
while (queue.Count > 0) {
var (x, y, keys, steps) = queue.Dequeue();
foreach (var (dx, dy) in dirs) {
int nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] != '#') {
char cell = grid[nx][ny];
// If it's a lock and we don't have the key, skip
if (char.IsUpper(cell) &&
(keys & (1 << (char.ToLower(cell) - 'a'))) == 0) {
continue;
}
int newKeys = keys;
// If it's a key, add it to our keyring
if (char.IsLower(cell)) {
newKeys |= 1 << (cell - 'a');
if (System.Numerics.BitOperations.PopCount((uint)newKeys) == keyCount) {
return steps + 1;
}
}
string state = $"{nx},{ny},{newKeys}";
if (!seen.Contains(state)) {
seen.Add(state);
queue.Enqueue((nx, ny, newKeys, steps + 1));
}
}
}
}
return -1;
}
} Implementation Notes:
- Uses BFS with state encoding for position and collected keys
- Uses bit manipulation for efficient key tracking
- Time complexity: O(m*n*2^k) where k is number of keys
- Space complexity: O(m*n*2^k)