Shortest Path to Get All Keys - Practice Coding Problems

Shortest Path to Get All Keys - 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.

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

Input & Output

Example 1 — Basic Key Collection

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

› Output: 8

💡 Note: Start at @, collect key 'a' (2 moves), go back to collect key 'b' (4 moves), then pass through locks A and B (2 more moves). Total: 8 moves.

Example 2 — Impossible Case

$ Input: grid = ["@..aA","..#..","....B"]

› Output: -1

💡 Note: Cannot reach key 'b' needed for lock 'B', so impossible to collect all keys.

Example 3 — No Keys

$ Input: grid = ["@...","...."]

› Output: 0

💡 Note: No keys to collect, so 0 moves needed.

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 30
grid[i][j] is one of '@', '.', '#', or a letter
1 ≤ number of keys ≤ 6

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Grid with start '@', keys (lowercase), locks (uppercase), walls '#'

BFS Search

Find shortest path collecting all keys while respecting lock constraints

Output

Minimum moves to collect all keys, or -1 if impossible

Key Takeaway

🎯 Key Insight: Use BFS with state (position + keys_collected) to find optimal path while respecting lock constraints

Asked in

G Google 45 a Amazon 38 M Microsoft 32 🍎 Apple 28

The key insight is to use BFS with state compression where each state represents both position and collected keys using bitmasks. Best approach is BFS with state tracking. Time: O(m×n×2^k), Space: O(m×n×2^k) where k ≤ 6.

Common Approaches

Approach	Time	Space	Notes
✓ BFS with State Tracking	O(m×n×2^k)	O(m×n×2^k)	Use BFS to find shortest path while tracking position and collected keys
Brute Force DFS	O(4^(m×n))	O(m×n)	Try all possible paths using DFS to find minimum moves to collect all keys

BFS with State Tracking — Algorithm Steps

Find start position and count total keys
Use BFS queue with states (row, col, keys_bitmask)
For each state, try all 4 directions
Check if we can pass locks and collect keys
Return moves when all keys collected

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize BFS

Start at '@' with empty key set, use queue for level-order traversal

Explore States

Each state = (position, keys_collected), check locks and collect keys

Find Shortest

BFS guarantees shortest path when all keys are collected

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_GRID 30
#define MAX_QUEUE 100000
#define MAX_VISITED 1000000

typedef struct {
    int r, c, keys, moves;
} State;

char grid[MAX_GRID][MAX_GRID];
int m, n, keyCount, targetKeys;
State queue[MAX_QUEUE];
int front, rear;
char visited[MAX_VISITED][50];
int visitedCount;

int isVisited(int r, int c, int keys) {
    char state[50];
    sprintf(state, "%d,%d,%d", r, c, keys);
    for (int i = 0; i < visitedCount; i++) {
        if (strcmp(visited[i], state) == 0) return 1;
    }
    return 0;
}

void addVisited(int r, int c, int keys) {
    sprintf(visited[visitedCount], "%d,%d,%d", r, c, keys);
    visitedCount++;
}

int solution(char gridInput[][MAX_GRID], int rows) {
    m = rows;
    n = strlen(gridInput[0]);
    for (int i = 0; i < m; i++) {
        strcpy(grid[i], gridInput[i]);
    }
    
    int startR = 0, startC = 0;
    keyCount = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '@') {
                startR = i; startC = j;
            } else if (grid[i][j] >= 'a' && grid[i][j] <= 'z') {
                keyCount++;
            }
        }
    }
    
    if (keyCount == 0) return 0;
    
    targetKeys = (1 << keyCount) - 1;
    front = rear = 0;
    visitedCount = 0;
    
    queue[rear++] = (State){startR, startC, 0, 0};
    addVisited(startR, startC, 0);
    
    int dirs[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    
    while (front < rear) {
        State curr = queue[front++];
        
        if (curr.keys == targetKeys) {
            return curr.moves;
        }
        
        for (int i = 0; i < 4; i++) {
            int nr = curr.r + dirs[i][0], nc = curr.c + dirs[i][1];
            
            if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                char cell = grid[nr][nc];
                
                if (cell == '#') continue;
                
                if (cell >= 'A' && cell <= 'Z') {
                    int keyNeeded = 1 << (cell - 'A');
                    if (!(curr.keys & keyNeeded)) continue;
                }
                
                int newKeys = curr.keys;
                if (cell >= 'a' && cell <= 'z') {
                    newKeys |= (1 << (cell - 'a'));
                }
                
                if (!isVisited(nr, nc, newKeys)) {
                    addVisited(nr, nc, newKeys);
                    queue[rear++] = (State){nr, nc, newKeys, curr.moves + 1};
                }
            }
        }
    }
    
    return -1;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    char gridInput[MAX_GRID][MAX_GRID];
    int rows = 0;
    
    char* token = strtok(line, "[\"]");
    while (token && rows < MAX_GRID) {
        if (strlen(token) > 0 && token[0] != ',' && token[0] != ']') {
            strcpy(gridInput[rows], token);
            rows++;
        }
        token = strtok(NULL, "[\"]");
    }
    
    printf("%d\n", solution(gridInput, rows));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n×2^k)

Each cell can be visited with different key combinations, k ≤ 6 keys means at most 64 states per cell

✓ Linear Growth

Space Complexity

O(m×n×2^k)

Queue and visited set store states for each cell-key combination

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

BFS with State Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler