864. 获取所有钥匙的最短路径

Hard

题目描述

给定一个 m x n 的网格 grid，其中：

'.' 是一个空的单元格。
'#' 是一堵墙。
'@' 是起始点。
小写字母代表钥匙。
大写字母代表锁。

你从起始点开始出发，一次移动是指向四个基本方向之一走一个空格。你不能走到网格外面，或者走到一堵墙上。

如果你走到一个钥匙上，你可以获得它。你不能走到锁上，除非你拥有对应的钥匙。

对于某个 1 <= k <= 6，网格中正好有英文字母表前 k 个字母的一个小写字母和一个大写字母。这意味着每个锁正好对应一个钥匙，每个钥匙正好对应一个锁；并且用来表示钥匙和锁的字母是按照英文字母表的顺序选择的。

返回获取所有钥匙所需要的最少移动次数。如果无法获取所有钥匙，返回 -1。

示例 1：

输入：grid = ["@.a..","###.#","b.A.B"]
输出：8
解释：注意，目标是获得所有的钥匙，而不是打开所有的锁。

示例 2：

输入：grid = ["@..aA","..B#.","....b"]
输出：6

示例 3：

输入：grid = ["@Aa"]
输出：-1

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 30
grid[i][j] 是英文字母、'.'、'#' 或 '@'。
网格中正好有一个 '@'。
网格中钥匙的数目在范围 [1, 6] 内。
网格中的每个钥匙都是唯一的。
网格中的每个钥匙都有匹配的锁。

解题思路

这是一个带状态的最短路径问题，需要同时考虑当前位置和已收集的钥匙状态。

核心思路：

状态定义：使用 (x, y, keys) 表示状态，其中 (x, y) 是当前位置，keys 是一个位掩码表示已收集的钥匙集合
位掩码优化：由于钥匙数量最多6个，可以用6位二进制数表示钥匙的收集状态，大大减少状态空间
BFS搜索：使用BFS保证找到的是最短路径，每次扩展当前状态到相邻的可达位置

算法流程：

预处理：找到起始位置和所有钥匙的位置，计算目标状态（所有钥匙都被收集）
BFS搜索：从起始状态开始，逐层扩展所有可能的状态
状态转移：对于每个状态，尝试向四个方向移动，检查新位置的合法性
终止条件：当达到目标状态时返回步数，队列为空时返回-1

关键细节：

使用三维visited数组 visited[x][y][keys] 避免重复访问相同状态
遇到锁时需检查是否有对应钥匙：keys & (1 << (c - 'A'))
遇到钥匙时更新状态：keys | (1 << (c - 'a'))

代码实现

class Solution {
public:
    int shortestPathAllKeys(vector<string>& grid) {
        int m = grid.size(), n = grid[0].size();
        int startX = -1, startY = -1, keyCount = 0;
        
        // 找起始位置和钥匙数量
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '@') {
                    startX = i;
                    startY = j;
                } else if (grid[i][j] >= 'a' && grid[i][j] <= 'f') {
                    keyCount++;
                }
            }
        }
        
        int allKeys = (1 << keyCount) - 1;
        vector<vector<vector<bool>>> visited(m, vector<vector<bool>>(n, vector<bool>(1 << keyCount, false)));
        
        queue<tuple<int, int, int, int>> q; // x, y, keys, steps
        q.push({startX, startY, 0, 0});
        visited[startX][startY][0] = true;
        
        int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (!q.empty()) {
            auto [x, y, keys, steps] = q.front();
            q.pop();
            
            if (keys == allKeys) {
                return steps;
            }
            
            for (int i = 0; i < 4; i++) {
                int nx = x + directions[i][0];
                int ny = y + directions[i][1];
                
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || grid[nx][ny] == '#') {
                    continue;
                }
                
                char c = grid[nx][ny];
                int newKeys = keys;
                
                // 遇到锁，检查是否有对应钥匙
                if (c >= 'A' && c <= 'F') {
                    if (!(keys & (1 << (c - 'A')))) {
                        continue;
                    }
                }
                // 遇到钥匙，更新状态
                else if (c >= 'a' && c <= 'f') {
                    newKeys |= (1 << (c - 'a'));
                }
                
                if (!visited[nx][ny][newKeys]) {
                    visited[nx][ny][newKeys] = true;
                    q.push({nx, ny, newKeys, steps + 1});
                }
            }
        }
        
        return -1;
    }
};

class Solution:
    def shortestPathAllKeys(self, grid: List[str]) -> int:
        m, n = len(grid), len(grid[0])
        start_x = start_y = key_count = 0
        
        # 找起始位置和钥匙数量
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '@':
                    start_x, start_y = i, j
                elif 'a' <= grid[i][j] <= 'f':
                    key_count += 1
        
        all_keys = (1 << key_count) - 1
        visited = set()
        
        queue = deque([(start_x, start_y, 0, 0)])  # x, y, keys, steps
        visited.add((start_x, start_y, 0))
        
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        while queue:
            x, y, keys, steps = queue.popleft()
            
            if keys == all_keys:
                return steps
            
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                
                if nx < 0 or nx >= m or ny < 0 or ny >= n or grid[nx][ny] == '#':
                    continue
                
                c = grid[nx][ny]
                new_keys = keys
                
                # 遇到锁，检查是否有对应钥匙
                if 'A' <= c <= 'F':
                    if not (keys & (1 << (ord(c) - ord('A')))):
                        continue
                # 遇到钥匙，更新状态
                elif 'a' <= c <= 'f':
                    new_keys |= (1 << (ord(c) - ord('a')))
                
                state = (nx, ny, new_keys)
                if state not in visited:
                    visited.add(state)
                    queue.append((nx, ny, new_keys, steps + 1))
        
        return -1

public class Solution {
    public int ShortestPathAllKeys(string[] grid) {
        int m = grid.Length, n = grid[0].Length;
        int startX = -1, startY = -1, keyCount = 0;
        
        // 找起始位置和钥匙数量
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '@') {
                    startX = i;
                    startY = j;
                } else if (grid[i][j] >= 'a' && grid[i][j] <= 'f') {
                    keyCount++;
                }
            }
        }
        
        int allKeys = (1 << keyCount) - 1;
        bool[,,] visited = new bool[m, n, 1 << keyCount];
        
        Queue<(int x, int y, int keys, int steps)> queue = new Queue<(int, int, int, int)>();
        queue.Enqueue((startX, startY, 0, 0));
        visited[startX, startY, 0] = true;
        
        int[,] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (queue.Count > 0) {
            var (x, y, keys, steps) = queue.Dequeue();
            
            if (keys == allKeys) {
                return steps;
            }
            
            for (int i = 0; i < 4; i++) {
                int nx = x + directions[i, 0];
                int ny = y + directions[i, 1];
                
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || grid[nx][ny] == '#') {
                    continue;
                }
                
                char c = grid[nx][ny];
                int newKeys = keys;
                
                // 遇到锁，检查是否有对应钥匙
                if (c >= 'A' && c <= 'F') {
                    if ((keys & (1 << (c - 'A'))) == 0) {
                        continue;
                    }
                }
                // 遇到钥匙，更新状态
                else if (c >= 'a' && c <= 'f') {
                    newKeys |= (1 << (c - 'a'));
                }
                
                if (!visited[nx, ny, newKeys]) {
                    visited[nx, ny, newKeys] = true;
                    queue.Enqueue((nx, ny, newKeys, steps + 1));
                }
            }
        }
        
        return -1;
    }
}

var shortestPathAllKeys = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    let start = null;
    let keyCount = 0;
    
    // Find start position and count keys
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === '@') {
                start = [i, j];
            } else if (grid[i][j] >= 'a' && grid[i][j] <= 'f') {
                keyCount++;
            }
        }
    }
    
    const allKeys = (1 << keyCount) - 1;
    const queue = [[start[0], start[1], 0, 0]]; // [row, col, keys, steps]
    const visited = new Set();
    visited.add(`${start[0]},${start[1]},0`);
    
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    
    while (queue.length > 0) {
        const [row, col, keys, steps] = queue.shift();
        
        if (keys === allKeys) {
            return steps;
        }
        
        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;
            
            if (newRow < 0 || newRow >= m || newCol < 0 || newCol >= n) {
                continue;
            }
            
            const cell = grid[newRow][newCol];
            
            if (cell === '#') {
                continue;
            }
            
            let newKeys = keys;
            
            // If it's a key
            if (cell >= 'a' && cell <= 'f') {
                const keyBit = 1 << (cell.charCodeAt(0) - 'a'.charCodeAt(0));
                newKeys |= keyBit;
            }
            
            // If it's a lock
            if (cell >= 'A' && cell <= 'F') {
                const lockBit = 1 << (cell.charCodeAt(0) - 'A'.charCodeAt(0));
                if (!(keys & lockBit)) {
                    continue;
                }
            }
            
            const state = `${newRow},${newCol},${newKeys}`;
            if (!visited.has(state)) {
                visited.add(state);
                queue.push([newRow, newCol, newKeys, steps + 1]);
            }
        }
    }
    
    return -1;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	大小
时间复杂度	O(m × n × 2^k)
空间复杂度	O(m × n × 2^k)

其中 m 和 n 分别是网格的行数和列数，k 是钥匙的数量（最多6个）。每个位置最多有 2^k 种不同的钥匙收集状态，BFS需要访问所有可能的状态组合。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析