LeetCode 每日一题笔记

0. 前言

• 日期：2026.04.27
• 题目：1391.检查网格中是否存在有效路径
• 难度：中等
• 标签：深度优先搜索、广度优先搜索、图、矩阵

1. 题目理解

问题描述：
给你一个 m x n 的网格 grid，每个单元格代表一条特定类型的街道，街道类型定义如下：

1. 连接单元格的左和右；
2. 连接单元格的上和下；
3. 连接单元格的左和下；
4. 连接单元格的右和下；
5. 连接单元格的左和上；
6. 连接单元格的右和上。

你从左上角 (0,0) 出发，目标是到达右下角 (m-1, n-1)，路径必须严格沿着街道的连接方向前进，且不能修改街道类型。如果存在这样的有效路径，返回 true，否则返回 false。

示例：

输入：grid = [[2,4,3],[6,5,2]] 输出：true 解释：存在一条从 (0,0) 到 (1,2) 的有效路径。

输入：grid = [[1,1,1,1,1,1,3]] 输出：true 解释：沿着水平街道一直向右，最终到达终点。

2. 解题思路

核心观察

• 这是一个图遍历问题，每个单元格是图的节点，街道的连接方向是节点间的边；
• 移动时必须满足双向连通：当前单元格的出口方向，必须与下一个单元格的入口方向匹配；
• 可使用深度优先搜索（DFS） 或广度优先搜索（BFS） 遍历所有可达单元格，判断是否能到达终点。

算法步骤

1. 定义方向与反向映射：
   • 定义四个方向（上、下、左、右）的坐标偏移；
   • 定义每个方向的反向方向（如“上”的反向是“下”，用于验证双向连通）；
   • 定义每种街道类型允许的出口方向。
2. DFS 遍历：
   • 从 (0,0) 开始，标记已访问单元格；
   • 对当前单元格，尝试所有允许的出口方向；
   • 计算下一个单元格坐标，判断是否越界、未被访问，且下一个单元格的入口方向与当前出口方向匹配；
   • 若匹配，递归访问下一个单元格；若到达终点，返回 true。
3. 结果判断：遍历完成后，若到达过终点则返回 true，否则返回 false。

3. 代码实现

package lc1391;

class lc1391.Solution {
    int[] dirX = {-1, 1, 0, 0};
    int[] dirY = {0, 0, -1, 1};
    int[] reverseDir = {1, 0, 3, 2};
    int[][] streets = {{}, {2, 3}, {0, 1}, {2, 1}, {3, 1}, {2, 0}, {3, 0}};

    public boolean hasValidPath(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        boolean[][] visited = new boolean[n][m];
        return dfs(grid, 0, 0, visited);
    }

    private boolean dfs(int[][] grid, int x, int y, boolean[][] visited) {
        int n = grid.length;
        int m = grid[0].length;
        visited[x][y] = true;
        if (x == n - 1 && y == m - 1) {
            return true;
        }
        int type = grid[x][y];
        for (int dir : streets[type]) {
            int nx = x + dirX[dir];
            int ny = y + dirY[dir];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
                int reverse = reverseDir[dir];
                int nextType = grid[nx][ny];
                for (int nd : streets[nextType]) {
                    if (nd == reverse) {
                        if (dfs(grid, nx, ny, visited)) {
                            return true;
                        }
                        break;
                    }
                }
            }
        }
        return false;
    }
}

4. 代码优化说明

优化点1：BFS 替代 DFS（避免递归栈溢出）

当网格较大时，DFS 递归可能导致栈溢出，可改用 BFS 实现：

public boolean hasValidPath(int[][] grid) {
    int n = grid.length;
    int m = grid[0].length;
    boolean[][] visited = new boolean[n][m];
    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[]{0, 0});
    visited[0][0] = true;
    while (!queue.isEmpty()) {
        int[] curr = queue.poll();
        int x = curr[0], y = curr[1];
        if (x == n - 1 && y == m - 1) return true;
        int type = grid[x][y];
        for (int dir : streets[type]) {
            int nx = x + dirX[dir];
            int ny = y + dirY[dir];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
                int reverse = reverseDir[dir];
                int nextType = grid[nx][ny];
                for (int nd : streets[nextType]) {
                    if (nd == reverse) {
                        visited[nx][ny] = true;
                        queue.add(new int[]{nx, ny});
                        break;
                    }
                }
            }
        }
    }
    return false;
}

优化点2：提前终止

在遍历过程中，一旦到达终点 (m-1, n-1)，立即返回 true，无需继续遍历。

优化点3：方向数组预定义

将街道类型、方向、反向方向全部预定义为数组，避免重复判断，提升代码可读性与执行效率。

5. 复杂度分析

• 时间复杂度：$O(m\times n)$

  • 每个单元格最多被访问一次，每次访问尝试 2 个方向，总操作数为线性级。

• 空间复杂度：$O(m\times n)$

  • 递归栈或 BFS 队列的最坏情况为整个网格大小；
  • 访问标记数组 visited 占用 $O(m\times n)$ 空间。

6. 总结

• 核心思路是图的遍历（DFS/BFS）+ 双向连通验证，通过预定义街道的连接方向，确保移动的合法性；
• 关键技巧：利用反向方向验证下一个单元格是否能接收当前方向的移动，避免无效遍历；
• 本题的核心难点是正确定义街道的连接方向，并处理双向连通的验证逻辑。

关键点回顾

1. 街道类型的连接方向需准确映射，每个类型对应两个出口方向；
2. 移动时必须验证双向连通，当前单元格的出口方向必须与下一个单元格的入口方向匹配；
3. DFS 与 BFS 均可解决，需根据网格大小选择合适的实现方式，避免栈溢出。