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:

1. Get the starting point and the count of the keys.
2. 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.
3. Begin BFS with a nested while loop to traverse all nodes in the same level before going to the next level.
4. 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.
5. Continue until we have visited all nodes or found a state that has collected all keys.
6. 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.