1391. 检查网格中是否存在有效路径

Medium

题目描述

给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是：

1 表示连接左单元格和右单元格的街道。
2 表示连接上单元格和下单元格的街道。
3 表示连接左单元格和下单元格的街道。
4 表示连接右单元格和下单元格的街道。
5 表示连接左单元格和上单元格的街道。
6 表示连接右单元格和上单元格的街道。

你最初会从左上角的街道（0, 0）开始出发。一个有效的路径是从左上角的单元格 (0, 0) 开始，到右下角的单元格 (m - 1, n - 1) 结束的路径。该路径必须沿着街道走。

注意：你不能更改任何街道。

如果网格中存在有效的路径，则返回 true，否则返回 false。

示例 1：

输入：grid = [[2,4,3],[6,5,2]]
输出：true
解释：如图所示，你可以从 (0, 0) 开始，访问网格的所有单元格，并到达 (m - 1, n - 1)。

示例 2：

输入：grid = [[1,2,1],[1,2,1]]
输出：false
解释：如图所示，单元格 (0, 0) 上的街道没有与任何其他单元格上的街道相连，你会在 (0, 0) 处卡住。

示例 3：

输入：grid = [[1,1,2]]
输出：false
解释：你会在单元格 (0, 1) 卡住，无法到达单元格 (0, 2)。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
1 <= grid[i][j] <= 6

解题思路

这道题的核心是判断从左上角到右下角是否存在一条连通的路径。我们需要根据每个单元格的街道类型来确定可以移动的方向。

解题思路：

建立连接关系：首先需要理解每种街道类型的连接方向。我们可以用方向数组来表示每种街道连接的两个方向。
路径验证：关键在于验证两个相邻单元格是否真正连通。当我们从单元格 A 移动到单元格 B 时，需要满足两个条件：
- A 的街道类型允许向 B 的方向移动
- B 的街道类型允许从 A 的方向进入
算法选择：可以使用 DFS、BFS 或并查集来解决。DFS 是最直观的选择，从起点开始遍历所有可达的单元格，检查是否能到达终点。
实现细节：
- 用二维数组记录每种街道类型的连接方向
- 使用 visited 数组避免重复访问
- 在 DFS 过程中验证相邻单元格的连通性

推荐解法：使用 DFS，因为它实现简单且空间效率较高。

代码实现

class Solution {
public:
    bool hasValidPath(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        
        // 定义每种街道的连接方向：上、右、下、左 (0,1,2,3)
        vector<vector<int>> directions = {
            {},           // 占位
            {1, 3},       // 1: 左右连接
            {0, 2},       // 2: 上下连接
            {2, 3},       // 3: 左下连接
            {1, 2},       // 4: 右下连接
            {0, 3},       // 5: 左上连接
            {0, 1}        // 6: 右上连接
        };
        
        // 方向向量：上、右、下、左
        vector<vector<int>> moves = {{-1,0}, {0,1}, {1,0}, {0,-1}};
        
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        
        function<bool(int, int)> dfs = [&](int x, int y) -> bool {
            if (x == m - 1 && y == n - 1) return true;
            
            visited[x][y] = true;
            
            // 获取当前单元格可以连接的方向
            for (int dir : directions[grid[x][y]]) {
                int nx = x + moves[dir][0];
                int ny = y + moves[dir][1];
                
                // 检查边界
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || visited[nx][ny]) 
                    continue;
                
                // 检查下一个单元格是否能从反方向连接回来
                int reverseDir = (dir + 2) % 4;
                bool canConnect = false;
                for (int nextDir : directions[grid[nx][ny]]) {
                    if (nextDir == reverseDir) {
                        canConnect = true;
                        break;
                    }
                }
                
                if (canConnect && dfs(nx, ny)) {
                    return true;
                }
            }
            
            return false;
        };
        
        return dfs(0, 0);
    }
};

class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        
        # 定义每种街道的连接方向：上、右、下、左 (0,1,2,3)
        directions = {
            1: [1, 3],    # 左右连接
            2: [0, 2],    # 上下连接  
            3: [2, 3],    # 左下连接
            4: [1, 2],    # 右下连接
            5: [0, 3],    # 左上连接
            6: [0, 1]     # 右上连接
        }
        
        # 方向向量：上、右、下、左
        moves = [(-1,0), (0,1), (1,0), (0,-1)]
        visited = [[False] * n for _ in range(m)]
        
        def dfs(x, y):
            if x == m - 1 and y == n - 1:
                return True
            
            visited[x][y] = True
            
            # 获取当前单元格可以连接的方向
            for direction in directions[grid[x][y]]:
                nx, ny = x + moves[direction][0], y + moves[direction][1]
                
                # 检查边界
                if nx < 0 or nx >= m or ny < 0 or ny >= n or visited[nx][ny]:
                    continue
                
                # 检查下一个单元格是否能从反方向连接回来
                reverse_dir = (direction + 2) % 4
                if reverse_dir in directions[grid[nx][ny]] and dfs(nx, ny):
                    return True
            
            return False
        
        return dfs(0, 0)

public class Solution {
    public bool HasValidPath(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        
        // 定义每种街道的连接方向：上、右、下、左 (0,1,2,3)
        var directions = new Dictionary<int, int[]> {
            {1, new int[]{1, 3}},  // 左右连接
            {2, new int[]{0, 2}},  // 上下连接
            {3, new int[]{2, 3}},  // 左下连接
            {4, new int[]{1, 2}},  // 右下连接
            {5, new int[]{0, 3}},  // 左上连接
            {6, new int[]{0, 1}}   // 右上连接
        };
        
        // 方向向量：上、右、下、左
        int[][] moves = new int[][] {
            new int[]{-1,0}, new int[]{0,1}, new int[]{1,0}, new int[]{0,-1}
        };
        
        bool[,] visited = new bool[m, n];
        
        bool Dfs(int x, int y) {
            if (x == m - 1 && y == n - 1) return true;
            
            visited[x, y] = true;
            
            // 获取当前单元格可以连接的方向
            foreach (int dir in directions[grid[x][y]]) {
                int nx = x + moves[dir][0];
                int ny = y + moves[dir][1];
                
                // 检查边界
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || visited[nx, ny]) 
                    continue;
                
                // 检查下一个单元格是否能从反方向连接回来
                int reverseDir = (dir + 2) % 4;
                bool canConnect = false;
                foreach (int nextDir in directions[grid[nx][ny]]) {
                    if (nextDir == reverseDir) {
                        canConnect = true;
                        break;
                    }
                }
                
                if (canConnect && Dfs(nx, ny)) {
                    return true;
                }
            }
            
            return false;
        }
        
        return Dfs(0, 0);
    }
}

var hasValidPath = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    
    const directions = {
        1: [[0, -1], [0, 1]], // left, right
        2: [[-1, 0], [1, 0]], // up, down
        3: [[0, -1], [1, 0]], // left, down
        4: [[1, 0], [0, 1]], // down, right
        5: [[-1, 0], [0, -1]], // up, left
        6: [[-1, 0], [0, 1]] // up, right
    };
    
    const visited = new Set();
    
    function dfs(row, col) {
        if (row === m - 1 && col === n - 1) return true;
        
        const key = `${row},${col}`;
        if (visited.has(key)) return false;
        visited.add(key);
        
        const streetType = grid[row][col];
        const possibleDirs = directions[streetType];
        
        for (const [dr, dc] of possibleDirs) {
            const newRow = row + dr;
            const newCol = col + dc;
            
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {
                const nextStreetType = grid[newRow][newCol];
                const nextDirs = directions[nextStreetType];
                
                // Check if the next cell connects back to current cell
                const backDir = [-dr, -dc];
                const canConnect = nextDirs.some(([ndr, ndc]) => ndr === backDir[0] && ndc === backDir[1]);
                
                if (canConnect && dfs(newRow, newCol)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    return dfs(0, 0);
};

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

复杂度分析

算法	时间复杂度	空间复杂度
DFS	O(m × n)	O(m × n)

时间复杂度：O(m × n)，其中 m 和 n 分别是网格的行数和列数。在最坏情况下需要访问所有单元格。
空间复杂度：O(m × n)，用于 visited 数组和递归调用栈的空间。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目