Leetcode 864. Shortest Path to Get All Keys
Problem Explanation
You are given a 2D grid, an ASCII representation of this grid is something like ["@.a.#","###.#","b.A.B"], where each character represents a different element of the grid. Here are the different types of characters and what they represent:
- "#" is a wall
- "." is an empty cell
- "@" is the starting point
- ("a", "b", ... "f") are keys
- ("A",ย "B", ... "F") are locks.
Our task starts at the starting point which is represented by "@", and we can move in one of the four cardinal directions for every move. We cannot move outside the grid, or into a wall. If we move over a key, we pick it up. However, we can't move over a lock unless we have the corresponding key.
The aim of the problem is to find the minimum number of moves to acquire all keys. If it's impossible, return -1.
Example
Consider the Grid: ["@..aA","..B#.","....b"]
Our starting point is "@", and we have to pick up all the keys and unlock all the locks.
In the first three moves, we go to the right and pick up the key "a". In the forth move, we move down. In the fifth move, we unlock "A" as we have its corresponding key. In the sixth move, we pick up the key "b".
So, the minimum number of moves to acquire all keys is 6.
Solution's Approach
The solution uses a Breadth-First Search (BFS) approach to traverse the 2D grid. BFS is a graph traversal algorithm that visits the nodes of a graph in breadth-wise order, meaning it visits the nodes level by level.
Explanation
The algorithm starts the BFS from the starting point "@" and maintains a queue to keep track of the nodes that need to be explored. A bitmask is used to indicate the keys that have been collected, so the same node with different sets of keys is treated as a different state.
Each time we pop a state from the front of the queue, we expand this state by exploring all valid moves in four directions: up, down, left, and right. If a move is valid (i.e., it does not go out of the grid or into a wall), and we have not visited this state before, we push it into the queue to be explored later.
The algorithm continues until it finds a state that has collected all the keys, at which point it returns the number of moves made, or until the queue is depleted, at which point it returns -1 as it's impossible to collect all the keys.
Algorithm Steps:
- Get the starting point and the count of the keys.
- Initialize a queue with the starting point and initialize a 3-dimensional
seen
array with the size of the grid to keep track of visited states. - Begin BFS with a nested while loop to traverse all nodes in the same level before going to the next level.
- For each state, explore all valid states in the grid. If we have not visited the new state before, we add it to the queue.
- Continue until we have visited all nodes or found a state that has collected all keys.
- If we have collected all keys, return the minimal number of moves, otherwise return -1.
Python Solution
1 2python 3from collections import deque 4 5class Solution: 6 def shortestPathAllKeys(self, grid): 7 # Find the start location and number of keys 8 start_i, start_j, num_keys = None, None, 0 9 for i, row in enumerate(grid): 10 for j, cell in enumerate(row): 11 if cell == "@": 12 start_i, start_j = i, j 13 elif cell.islower(): 14 num_keys += 1 15 16 # State is current i, j, and keys we have 17 start_state = (start_i, start_j, 0) 18 # Queue for BFS 19 queue = deque([(start_state, 0)]) 20 # Set for seen states 21 seen = set([start_state]) 22 23 while queue: 24 (i, j, keys), steps = queue.popleft() 25 # If we find a key, add it to our keys 26 if grid[i][j].islower(): 27 keys |= (1 << (ord(grid[i][j]) - ord("a"))) 28 # If we found all keys, return steps 29 if keys == (1 << num_keys) - 1: 30 return steps 31 for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)): 32 # If out of bounds, skip 33 if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]): 34 continue 35 # If wall or lock we don't have key for, skip 36 if grid[x][y] == "#" or (grid[x][y].isupper() and not keys & (1 << (ord(grid[x][y]) - ord("A")))): 37 continue 38 # Add new state to queue 39 new_state = (x, y, keys) 40 if new_state not in seen: 41 seen.add(new_state) 42 queue.append((new_state, steps+1)) 43 # Didn't find a solution 44 return -1
In the Python solution, queue
is a double-ended queue to keep track of nodes that need to be visited. seen
is a set to keep track of which states have been visited before. A bitwise operation is used to add and check the collected keys. If we find a state that has collected all keys, we return the smallest number of moves, otherwise return -1.## JavaScript Solution
JavaScript solution follows the same BFS approach but with some additional operations required to mimic bitwise operations due to JavaScript treating bitwise operations as 32-bit integers.
Below is the JavaScript version of solving the problem:
1
2javascript
3class Solution {
4 shortestPathAllKeys(grid) {
5 let start_i, start_j, num_keys = 0;
6 for (let i = 0; i < grid.length; i++) {
7 for (let j = 0; j < grid[i].length; j++) {
8 if (grid[i][j] == "@") {
9 start_i = i;
10 start_j = j;
11 } else if (grid[i][j].toLowerCase() != grid[i][j]) {
12 num_keys += 1;
13 }
14 }
15 }
16
17 const queue = [[start_i, start_j, 0]];
18 const seen = new Set([start_i + "," + start_j + ",0"]);
19 let steps = 0;
20
21 while (queue.length) {
22 let size = queue.length;
23 while (size-- > 0) {
24 let [i, j, keys] = queue.shift();
25 if (grid[i][j].toLowerCase() != grid[i][j]) {
26 keys = keys | (1 << (grid[i][j].charCodeAt() - "a".charCodeAt()));
27 if (keys == (2 ** num_keys) - 1) {
28 return steps;
29 }
30 }
31 for (let [dx, dy] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
32 let ni = i + dx, nj = j + dy;
33 if (ni < 0 || ni >= grid.length || nj < 0 || nj >= grid[0].length || grid[ni][nj] == "#") {
34 continue;
35 }
36 let lock = grid[ni][nj].toUpperCase();
37 if (grid[ni][nj] == lock && !(keys & (1 << (lock.charCodeAt() - "A".charCodeAt())))) {
38 continue;
39 }
40 let state = ni + "," + nj + "," + keys;
41 if (!seen.has(state)) {
42 seen.add(state);
43 queue.push([ni, nj, keys]);
44 }
45 }
46 }
47 steps += 1;
48 }
49 return -1;
50 }
51}
In the JS version, variables start_i
and start_j
store the starting point, and num_keys
count the total number of keys. The queue and seen set maintain the BFS loop and state checking. A bitwise operation is performed on the keys to add new keys to the found list.
Java Solution
The Java approach is again very similar to BFS. Here's how it can be implemented:
1 2java 3import java.util.*; 4 5class Solution { 6 public int shortestPathAllKeys(String[] grid) { 7 int start_i = 0, start_j = 0, max_keys = 0; 8 for (int i = 0; i < grid.length; i++) { 9 for (int j = 0; j < grid[i].length(); j++) { 10 char c = grid[i].charAt(j); 11 if (c == '@') { 12 start_i = i; 13 start_j = j; 14 } else if (c >= 'a' && c <= 'f') { 15 max_keys = Math.max(max_keys, c - 'a' + 1); 16 } 17 } 18 } 19 20 Queue<int[]> queue = new LinkedList<>(); 21 queue.offer(new int[]{start_i, start_j, 0}); 22 boolean[][][] visited = new boolean[grid.length][grid[0].length()][1 << max_keys]; 23 visited[start_i][start_j][0] = true; 24 int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; 25 int steps = 0; 26 27 while (!queue.isEmpty()) { 28 for (int k = queue.size(); k > 0; k--) { 29 int[] node = queue.poll(); 30 int i = node[0]; 31 int j = node[1]; 32 int keys = node[2]; 33 char c = grid[i].charAt(j); 34 35 if (c >= 'a' && c <= 'f') { 36 keys |= (1 << (c - 'a')); 37 if (keys == (1 << max_keys) - 1) { 38 return steps; 39 } 40 } 41 42 for (int[] dir : dirs) { 43 int ni = i + dir[0]; 44 int nj = j + dir[1]; 45 if (ni >= 0 && ni < grid.length && nj >= 0 && nj < grid[0].length() && 46 grid[ni].charAt(nj) != '#' && 47 !(grid[ni].charAt(nj) >= 'A' && grid[ni].charAt(nj) <= 'F' && 48 ((keys >> (grid[ni].charAt(nj) - 'A')) & 1) == 0)) { 49 if (!visited[ni][nj][keys]) { 50 queue.offer(new int[]{ni, nj, keys}); 51 visited[ni][nj][keys] = true; 52 } 53 } 54 } 55 } 56 steps++; 57 } 58 return -1; 59 } 60}
The Java version uses a queue to handle the BFS traversal and a 3D boolean array to keep track of the visited states. The bitwise operations are quite similar to the ones in Python and JS to handle the keys.
That concludes the coverage on solving the Keys and Locks problem using Breadth-First Search in Python, JavaScript and Java.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.