Problem

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.

For some 1 <= k <= 6, there is exactly one lowercase and one uppercase letter of the first k letters of the English alphabet in the grid. This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.

Return the lowest number of moves to acquire all keys. If it is impossible, return -1.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4

Input:
grid = ["@..aA","..B#.","....b"]
Output:
 6

Example 3:

1
2
3
4

Input:
grid = ["@Aa"]
Output:
 -1

Solution

Method 1 – BFS with State Encoding

Intuition

The problem is to find the shortest path to collect all keys in a grid with walls, locks, and keys. Since the state depends on both position and which keys have been collected, we use BFS and encode the state as (row, col, keys_bitmask).

Approach

  1. Find the starting position and count the total number of keys in the grid.
  2. Use BFS with a queue storing (row, col, keys_bitmask, steps).
  3. For each move, if the cell is a key, update the keys_bitmask.
  4. If the cell is a lock, only proceed if the corresponding key is collected.
  5. Use a 3D visited array to avoid revisiting the same state.
  6. When all keys are collected, return the number of steps.
  7. If not possible, return -1.

Code

Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution {
    public int shortestPathAllKeys(String[] grid) {
        int m = grid.length, n = grid[0].length(), allKeys = 0, sx = 0, sy = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                char c = grid[i].charAt(j);
                if (c == '@') { sx = i; sy = j; }
                if (c >= 'a' && c <= 'f') allKeys |= 1 << (c - 'a');
            }
        }
        boolean[][][] vis = new boolean[m][n][1 << 6];
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{sx, sy, 0, 0});
        vis[sx][sy][0] = true;
        int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0], y = cur[1], keys = cur[2], steps = cur[3];
            if (keys == allKeys) return steps;
            for (int[] d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                char nc = grid[nx].charAt(ny);
                if (nc == '#') continue;
                int nkeys = keys;
                if (nc >= 'a' && nc <= 'f') nkeys |= 1 << (nc - 'a');
                if (nc >= 'A' && nc <= 'F' && (nkeys & (1 << (nc - 'A'))) == 0) continue;
                if (!vis[nx][ny][nkeys]) {
                    vis[nx][ny][nkeys] = true;
                    q.offer(new int[]{nx, ny, nkeys, steps + 1});
                }
            }
        }
        return -1;
    }
}

Complexity

  • ⏰ Time complexity: O(m * n * 2^k), where k is the number of keys, since each state is (row, col, keys_bitmask).
  • 🧺 Space complexity: O(m * n * 2^k), for the visited array and queue.

Method 2 – BFS with Priority Queue (Dijkstra)

Intuition

We can use a priority queue to always expand the shortest path first, similar to Dijkstra’s algorithm, but the BFS approach is usually sufficient for unweighted grids.

Approach

  1. Same as Method 1, but use a priority queue to store states by steps.
  2. Always expand the state with the smallest steps.
  3. Otherwise, logic is the same as Method 1.

Code

Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

import java.util.*;
class Solution {
    public int shortestPathAllKeys(String[] grid) {
        int m = grid.length, n = grid[0].length(), allKeys = 0, sx = 0, sy = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                char c = grid[i].charAt(j);
                if (c == '@') { sx = i; sy = j; }
                if (c >= 'a' && c <= 'f') allKeys |= 1 << (c - 'a');
            }
        }
        boolean[][][] vis = new boolean[m][n][1 << 6];
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[3]));
        pq.offer(new int[]{sx, sy, 0, 0});
        vis[sx][sy][0] = true;
        int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int x = cur[0], y = cur[1], keys = cur[2], steps = cur[3];
            if (keys == allKeys) return steps;
            for (int[] d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                char nc = grid[nx].charAt(ny);
                if (nc == '#') continue;
                int nkeys = keys;
                if (nc >= 'a' && nc <= 'f') nkeys |= 1 << (nc - 'a');
                if (nc >= 'A' && nc <= 'F' && (nkeys & (1 << (nc - 'A'))) == 0) continue;
                if (!vis[nx][ny][nkeys]) {
                    vis[nx][ny][nkeys] = true;
                    pq.offer(new int[]{nx, ny, nkeys, steps + 1});
                }
            }
        }
        return -1;
    }
}

Complexity

  • ⏰ Time complexity: O(m * n * 2^k), same as BFS, but with extra log factor for priority queue operations.
  • 🧺 Space complexity: O(m * n * 2^k).