LeetCode 864 - Shortest Path to Get All Keys

LeetCode Problem 864

Difficulty: 🔴 Hard
Topics: Array, Bit Manipulation, Breadth-First Search, Matrix

Solution

Problem Understanding

This problem asks us to find the shortest path to collect all keys in a 2D grid maze. The grid contains walls, open spaces, keys, locks, and a starting point. You can move in the four cardinal directions but cannot move diagonally, through walls, or outside the grid. Each lock can only be passed if the corresponding key has been collected. The grid guarantees that each key has exactly one corresponding lock and vice versa, with keys labeled from 'a' to 'f' and locks labeled from 'A' to 'F'.

The input is a list of strings representing the grid. Each character encodes the cell type. The output is a single integer, representing the minimum number of steps required to collect all keys. If it is impossible to collect all keys, the output should be -1.

Constraints tell us the grid size is small to medium (1 <= m, n <= 30) and the number of keys is limited (1 <= k <= 6). This limited number of keys is crucial because it allows us to represent the set of collected keys efficiently using bit manipulation. Important edge cases include grids where keys are unreachable due to walls, all keys are on the starting cell, or locks block essential paths.

Approaches

A naive brute-force approach would explore all possible sequences of moves from the starting position, considering every possible order of collecting keys. This could be done using recursive backtracking with a visited set to avoid revisiting the same state. Although this would give the correct answer, it is computationally infeasible because the number of states grows exponentially with the grid size and the number of keys. Specifically, there could be up to m*n * 2^k states, which is too large to explore without optimization.

The key insight for an optimal solution is to treat this as a shortest path problem in a state space defined by (row, col, keys_collected). Breadth-First Search (BFS) naturally finds the shortest path in an unweighted graph, and we can encode collected keys as a bitmask to efficiently track which keys we have collected. BFS ensures that we explore all possible moves level by level, guaranteeing that the first time we reach the state with all keys, it is through the shortest path. By using a set to track visited states (row, col, keys_bitmask), we avoid revisiting redundant states and prune the search space drastically.

Algorithm Walkthrough

1. Initialization: Scan the grid to locate the starting position @ and count the total number of keys. Encode each key as a bitmask position (0 for 'a', 1 for 'b', etc.) so that the set of collected keys can be stored as an integer.
2. State Representation: Define the BFS state as (row, col, keys_bitmask), where keys_bitmask is an integer with bits set for each collected key. For example, if keys 'a' and 'c' are collected, keys_bitmask is 0b101.
3. BFS Queue and Visited Set: Initialize a queue with the starting state (start_row, start_col, 0) and a visited set to keep track of already explored states (row, col, keys_bitmask). This prevents revisiting states and guarantees BFS efficiency.
4. BFS Iteration: Process the queue in a level-order manner to count steps. For each state, consider moving in the four cardinal directions. Ignore moves that go out of bounds or hit a wall '#'.
5. Key Collection: If a new position contains a key, update the keys_bitmask by setting the corresponding bit.
6. Lock Check: If a new position contains a lock, check if the corresponding key has been collected. Only enqueue the move if the key is present in the keys_bitmask.
7. Completion Check: If the updated keys_bitmask equals (1 << total_keys) - 1, return the number of steps taken, since all keys have been collected.
8. Queue Update: Enqueue the new state if it has not been visited before.
9. Termination: If the queue becomes empty without collecting all keys, return -1 to indicate it is impossible.

Why it works: BFS guarantees the shortest path in unweighted graphs because it explores states level by level. By including the keys bitmask in the state, BFS ensures that the first time we reach a state with all keys collected, it is through the shortest possible path.

Python Solution

from collections import deque
from typing import List

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m, n = len(grid), len(grid[0])
        all_keys = 0
        start_row = start_col = 0
        
        # Find start and total keys
        for i in range(m):
            for j in range(n):
                char = grid[i][j]
                if char == '@':
                    start_row, start_col = i, j
                elif 'a' <= char <= 'f':
                    all_keys |= (1 << (ord(char) - ord('a')))
        
        # BFS
        queue = deque([(start_row, start_col, 0)])
        visited = set((start_row, start_col, 0))
        steps = 0
        directions = [(0,1),(1,0),(0,-1),(-1,0)]
        
        while queue:
            for _ in range(len(queue)):
                row, col, keys = queue.popleft()
                if keys == all_keys:
                    return steps
                for dr, dc in directions:
                    r, c = row + dr, col + dc
                    if 0 <= r < m and 0 <= c < n:
                        cell = grid[r][c]
                        if cell == '#':
                            continue
                        new_keys = keys
                        if 'a' <= cell <= 'f':
                            new_keys |= (1 << (ord(cell) - ord('a')))
                        if 'A' <= cell <= 'F' and not (keys & (1 << (ord(cell) - ord('A')))):
                            continue
                        state = (r, c, new_keys)
                        if state not in visited:
                            visited.add(state)
                            queue.append(state)
            steps += 1
        
        return -1

This Python implementation initializes the BFS queue with the starting position and a bitmask of zero keys. It processes the queue level by level, updating the keys bitmask whenever a key is collected and only allowing movement through locks if the corresponding key has been collected. The visited set prevents reprocessing redundant states, ensuring BFS explores each unique state once. When all keys are collected, the number of steps taken is returned.

Go Solution

package main

import "container/list"

func shortestPathAllKeys(grid []string) int {
    m, n := len(grid), len(grid[0])
    var allKeys int
    startRow, startCol := 0, 0
    
    // Find start and total keys
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            char := grid[i][j]
            if char == '@' {
                startRow, startCol = i, j
            } else if char >= 'a' && char <= 'f' {
                allKeys |= 1 << (char - 'a')
            }
        }
    }
    
    type state struct {
        row, col, keys int
    }
    
    queue := list.New()
    queue.PushBack(state{startRow, startCol, 0})
    visited := make(map[state]bool)
    visited[state{startRow, startCol, 0}] = true
    steps := 0
    directions := [][2]int{{0,1},{1,0},{0,-1},{-1,0}}
    
    for queue.Len() > 0 {
        for size := queue.Len(); size > 0; size-- {
            front := queue.Remove(queue.Front()).(state)
            row, col, keys := front.row, front.col, front.keys
            if keys == allKeys {
                return steps
            }
            for _, d := range directions {
                r, c := row + d[0], col + d[1]
                if r >= 0 && r < m && c >= 0 && c < n {
                    cell := grid[r][c]
                    if cell == '#' {
                        continue
                    }
                    newKeys := keys
                    if cell >= 'a' && cell <= 'f' {
                        newKeys |= 1 << (cell - 'a')
                    }
                    if cell >= 'A' && cell <= 'F' && (keys&(1<<(cell-'A')) == 0) {
                        continue
                    }
                    newState := state{r, c, newKeys}
                    if !visited[newState] {
                        visited[newState] = true
                        queue.PushBack(newState)
                    }
                }
            }
        }
        steps++
    }
    
    return -1
}