3552. 网格传送遍历

Medium

题目描述

给你一个大小为 m x n 的二维字符网格矩阵，表示为字符串数组，其中 matrix[i][j] 表示第 i 行第 j 列交叉处的单元格。每个单元格是以下之一：

‘.’ 表示空单元格。
‘#’ 表示障碍物。
大写字母（‘A’-‘Z’）表示传送门。

你从左上角单元格 (0, 0) 开始，目标是到达右下角单元格 (m - 1, n - 1)。你可以从当前单元格移动到任何相邻单元格（上、下、左、右），只要目标单元格在网格边界内且不是障碍物。

如果你踩到包含传送门字母的单元格，并且你之前没有使用过该传送门字母，你可以立即传送到网格中具有相同字母的任何其他单元格。这种传送不计为移动，但每个传送门字母在你的旅程中最多只能使用一次。

返回到达右下角单元格所需的最小移动次数。如果无法到达目标，返回 -1。

示例 1:

输入: matrix = ["A..",".A.","..."]
输出: 2
解释:
- 在第一步移动之前，从 (0, 0) 传送到 (1, 1)。
- 第一步移动，从 (1, 1) 移动到 (1, 2)。
- 第二步移动，从 (1, 2) 移动到 (2, 2)。

示例 2:

输入: matrix = [".#...",".#.#.",".#.#.","...#."]
输出: 13

约束条件:

1 <= m == matrix.length <= 10³
1 <= n == matrix[i].length <= 10³
matrix[i][j] 是 ‘#’、’.’ 或大写英文字母
matrix[0][0] 不是障碍物

解题思路

这是一个最短路径问题，需要考虑传送门的特殊机制。我们可以使用BFS来解决。

核心思路：

将每个传送门字母看作一个虚拟的"超级节点"，所有相同字母的位置都连接到这个超级节点
当我们第一次到达某个传送门时，可以免费传送到该字母的任何其他位置
使用BFS确保找到最短路径，状态需要记录当前位置和已使用的传送门

算法步骤：

预处理所有传送门位置，建立字母到位置列表的映射
使用BFS，状态包括 (行, 列, 已使用传送门的位掩码)
对于每个状态，尝试四个方向的移动
如果当前位置是未使用的传送门，将所有相同字母的位置加入队列
当到达目标位置时返回步数

推荐解法： 使用位掩码记录已使用传送门的BFS解法，时间复杂度较优。

代码实现

class Solution {
public:
    int minMoves(vector<string>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        
        // 收集所有传送门位置
        unordered_map<char, vector<pair<int, int>>> portals;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                char c = matrix[i][j];
                if (c >= 'A' && c <= 'Z') {
                    portals[c].push_back({i, j});
                }
            }
        }
        
        // BFS: {row, col, used_portals_mask}
        queue<tuple<int, int, int, int>> q; // row, col, mask, moves
        set<tuple<int, int, int>> visited;
        
        q.push({0, 0, 0, 0});
        visited.insert({0, 0, 0});
        
        int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (!q.empty()) {
            auto [row, col, mask, moves] = q.front();
            q.pop();
            
            if (row == m - 1 && col == n - 1) {
                return moves;
            }
            
            // 尝试四个方向移动
            for (auto& dir : dirs) {
                int nr = row + dir[0], nc = col + dir[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && 
                    matrix[nr][nc] != '#') {
                    if (visited.find({nr, nc, mask}) == visited.end()) {
                        visited.insert({nr, nc, mask});
                        q.push({nr, nc, mask, moves + 1});
                    }
                }
            }
            
            // 尝试传送门
            char c = matrix[row][col];
            if (c >= 'A' && c <= 'Z') {
                int portal_bit = c - 'A';
                if (!(mask & (1 << portal_bit))) { // 未使用过这个传送门
                    int new_mask = mask | (1 << portal_bit);
                    for (auto& [pr, pc] : portals[c]) {
                        if (visited.find({pr, pc, new_mask}) == visited.end()) {
                            visited.insert({pr, pc, new_mask});
                            q.push({pr, pc, new_mask, moves});
                        }
                    }
                }
            }
        }
        
        return -1;
    }
};

class Solution:
    def minMoves(self, matrix: List[str]) -> int:
        m, n = len(matrix), len(matrix[0])
        
        # 收集所有传送门位置
        portals = {}
        for i in range(m):
            for j in range(n):
                c = matrix[i][j]
                if c.isupper():
                    if c not in portals:
                        portals[c] = []
                    portals[c].append((i, j))
        
        # BFS: (row, col, used_portals_mask, moves)
        from collections import deque
        queue = deque([(0, 0, 0, 0)])
        visited = set([(0, 0, 0)])
        
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        while queue:
            row, col, mask, moves = queue.popleft()
            
            if row == m - 1 and col == n - 1:
                return moves
            
            # 尝试四个方向移动
            for dr, dc in dirs:
                nr, nc = row + dr, col + dc
                if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] != '#':
                    if (nr, nc, mask) not in visited:
                        visited.add((nr, nc, mask))
                        queue.append((nr, nc, mask, moves + 1))
            
            # 尝试传送门
            c = matrix[row][col]
            if c.isupper():
                portal_bit = ord(c) - ord('A')
                if not (mask & (1 << portal_bit)):  # 未使用过这个传送门
                    new_mask = mask | (1 << portal_bit)
                    for pr, pc in portals[c]:
                        if (pr, pc, new_mask) not in visited:
                            visited.add((pr, pc, new_mask))
                            queue.append((pr, pc, new_mask, moves))
        
        return -1

public class Solution {
    public int MinMoves(string[] matrix) {
        int m = matrix.Length, n = matrix[0].Length;
        
        // 收集所有传送门位置
        var portals = new Dictionary<char, List<(int, int)>>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                char c = matrix[i][j];
                if (char.IsUpper(c)) {
                    if (!portals.ContainsKey(c)) {
                        portals[c] = new List<(int, int)>();
                    }
                    portals[c].Add((i, j));
                }
            }
        }
        
        // BFS
        var queue = new Queue<(int row, int col, int mask, int moves)>();
        var visited = new HashSet<(int, int, int)>();
        
        queue.Enqueue((0, 0, 0, 0));
        visited.Add((0, 0, 0));
        
        int[,] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (queue.Count > 0) {
            var (row, col, mask, moves) = queue.Dequeue();
            
            if (row == m - 1 && col == n - 1) {
                return moves;
            }
            
            // 尝试四个方向移动
            for (int d = 0; d < 4; d++) {
                int nr = row + dirs[d, 0], nc = col + dirs[d, 1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && 
                    matrix[nr][nc] != '#') {
                    if (!visited.Contains((nr, nc, mask))) {
                        visited.Add((nr, nc, mask));
                        queue.Enqueue((nr, nc, mask, moves + 1));
                    }
                }
            }
            
            // 尝试传送门
            char c = matrix[row][col];
            if (char.IsUpper(c)) {
                int portalBit = c - 'A';
                if ((mask & (1 << portalBit)) == 0) { // 未使用过这个传送门
                    int newMask = mask | (1 << portalBit);
                    if (portals.ContainsKey(c)) {
                        foreach (var (pr, pc) in portals[c]) {
                            if (!visited.Contains((pr, pc, newMask))) {
                                visited.Add((pr, pc, newMask));
                                queue.Enqueue((pr, pc, newMask, moves));
                            }
                        }
                    }
                }
            }
        }
        
        return -1;
    }
}

var minMoves = function(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    
    // Find all portal positions
    const portals = new Map();
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const cell = matrix[i][j];
            if (cell >= 'A' && cell <= 'Z') {
                if (!portals.has(cell)) {
                    portals.set(cell, []);
                }
                portals.get(cell).push([i, j]);
            }
        }
    }
    
    // BFS with state (row, col, usedPortals)
    const queue = [[0, 0, new Set(), 0]]; // [row, col, usedPortals, moves]
    const visited = new Set();
    visited.add('0,0,' + Array.from(new Set()).sort().join(''));
    
    while (queue.length > 0) {
        const [row, col, usedPortals, moves] = queue.shift();
        
        if (row === m - 1 && col === n - 1) {
            return moves;
        }
        
        const currentCell = matrix[row][col];
        
        // Try teleportation if current cell is a portal and not used
        if (currentCell >= 'A' && currentCell <= 'Z' && !usedPortals.has(currentCell)) {
            const newUsedPortals = new Set(usedPortals);
            newUsedPortals.add(currentCell);
            
            if (portals.has(currentCell)) {
                for (const [portalRow, portalCol] of portals.get(currentCell)) {
                    if (portalRow !== row || portalCol !== col) {
                        const stateKey = portalRow + ',' + portalCol + ',' + Array.from(newUsedPortals).sort().join('');
                        if (!visited.has(stateKey)) {
                            visited.add(stateKey);
                            queue.push([portalRow, portalCol, newUsedPortals, moves]);
                        }
                    }
                }
            }
        }
        
        // Try regular moves
        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;
            
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && matrix[newRow][newCol] !== '#') {
                const stateKey = newRow + ',' + newCol + ',' + Array.from(usedPortals).sort().join('');
                if (!visited.has(stateKey)) {
                    visited.add(stateKey);
                    queue.push([newRow, newCol, usedPortals, moves + 1]);
                }
            }
        }
    }
    
    return -1;
};

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

复杂度分析

复杂度类型	值
时间复杂度	O(m × n × 2^26)
空间复杂度	O(m × n × 2^26)

注：虽然理论复杂度包含 2^26，但实际运行中传送门数量通常远少于26个，且每个传送门只能使用一次，实际复杂度会大大降低。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析