Course4all
Join us on telegram
Home/dsa/Graphs/Shortest Path to Get All Keys

Shortest Path to Get All Keys

Master this topic with zero to advance depth.

Shortest Path to Get All Keys

You are given an m x n grid grid where:

  • '.' is an empty cell.
  • '#' is a wall.
  • '@' is the starting point.
  • lowercase letters are keys.
  • uppercase letters are 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 through a wall. If you walk over a key, you pick it up. If you walk over a lock and have the matching key, you can pass through it.

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

Visual Representation

Grid: @ . a . # # # # . # b . A . B Starting at @. Path: 1. Pick 'a' 2. Use 'a' to open 'A' 3. Pick 'b' Done! Return shortest path length.
Hard

Examples

Input: grid = ["@.a.#","###.#","b.A.B"]
Output: 8

Shortest path to pick up all keys 'a' and 'b'.

Approach 1

Level III: Optimal (BFS with State - Bitmask)

Intuition

The 'state' of our BFS is not just our position (r, c), but also which keys we possess. We can represent the set of obtained keys as a bitmask. This turns the problem into a standard shortest path BFS in a state space of (r, c, mask).

Thought Process

  1. Find start position @ and count total number of keys K.
  2. Target mask is (1 << K) - 1.
  3. Queue stores (r, c, mask, distance).
  4. visited[r][c][mask] tracks seen states.
  5. In each step:
    • If current cell is a key, update newMask = mask | (1 << (key - 'a')).
    • If newMask == targetMask, return dist.
    • If current cell is a lock and we don't have the key, skip.
    • Standard 4-direction BFS flow.

Pattern: BFS with State Bitmasking

⏱ O(M * N * 2^K) where K is number of keys.💾 O(M * N * 2^K) for visited array.

Detailed Dry Run

2 keys. Target mask = 11 (3). Start (0,0) mask 00.

  • Reach 'a' (0,2). Mask = 01.
  • Reach 'A' (2,2). Lock 'A' (bit 0) matches mask bit 0. Passage allowed.
  • Reach 'b' (2,0). Mask = 11. Target reached!
java
import java.util.*;

public class Main {
    public static int shortestPathAllKeys(String[] grid) {
        int m = grid.length, n = grid[0].length();
        int startR = -1, startC = -1, totalKeys = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                char c = grid[i].charAt(j);
                if (c == '@') { startR = i; startC = j; }
                else if (c >= 'a' && c <= 'f') totalKeys++;
            }
        }

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{startR, startC, 0, 0});
        boolean[][][] visited = new boolean[m][n][1 << totalKeys];
        visited[startR][startC][0] = true;

        int[][] dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int r = curr[0], c = curr[1], mask = curr[2], dist = curr[3];
            if (mask == (1 << totalKeys) - 1) return dist;

            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    char next = grid[nr].charAt(nc);
                    if (next == '#') continue;
                    int nextMask = mask;
                    if (next >= 'a' && next <= 'f') nextMask |= (1 << (next - 'a'));
                    if (next >= 'A' && next <= 'F' && (mask & (1 << (next - 'A'))) == 0) continue;
                    
                    if (!visited[nr][nc][nextMask]) {
                        visited[nr][nc][nextMask] = true;
                        q.offer(new int[]{nr, nc, nextMask, dist + 1});
                    }
                }
            }
        }
        return -1;
    }
}
← Previous QuestionReconstruct Itinerary
Next Question →Find the City With the Smallest Number of Neighbors at a Threshold Distance