解题思路

本题要求判断能否从网格左上角 (0, 0) 走到右下角 (m-1, n-1)，其中每个格子代表一种街道类型（1~6），每种街道只允许特定方向通行。

核心思想是使用 BFS（广度优先搜索） 遍历所有可达位置，并在移动时验证 双向连通性：即当前格子允许通往下一格，且下一格也允许从当前格进入。

代码解析

class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        
        # 定义6种街道类型各自允许的两个通行方向（dx, dy）
        di = [
            [(0, 1), (0, -1)],  # 类型1：左右
            [(1, 0), (-1, 0)],  # 类型2：上下
            [(0, -1), (1, 0)],  # 类型3：左、下
            [(0, 1), (1, 0)],   # 类型4：右、下
            [(0, -1), (-1, 0)], # 类型5：左、上
            [(0, 1), (-1, 0)]   # 类型6：右、上
        ]

        # 访问标记数组，防止重复访问
        vis = [[False] * n for _ in range(m)]
        q = deque([(0, 0)])
        vis[0][0] = True

        def check(x, y, nx, ny):
            """检查从 (x,y) 到 (nx,ny) 是否双向连通"""
            dx, dy = nx - x, ny - y                # 当前移动方向
            idx1, idx2 = grid[x][y], grid[nx][ny]  # 获取两个格子的街道类型
            dirs1 = di[idx1 - 1]                   # 当前格允许的方向
            dirs2 = di[idx2 - 1]                   # 下一格允许的方向
            # 必须满足：当前格能往 (dx,dy) 走，且下一格能往反方向 (-dx,-dy) 走
            return (dx, dy) in dirs1 and (-dx, -dy) in dirs2

        while q:
            x, y = q.popleft()
            # 遍历当前格子所有可能的出边方向
            for dx, dy in di[grid[x][y] - 1]:
                nx, ny = x + dx, y + dy
                # 边界检查 + 未访问 + 双向连通
                if 0 <= nx < m and 0 <= ny < n and not vis[nx][ny]:
                    if check(x, y, nx, ny):
                        q.append((nx, ny))
                        vis[nx][ny] = True
        
        return vis[m-1][n-1]  # 若终点被访问过，则存在有效路径

关键点
街道建模：将6种街道抽象为方向对，便于程序处理。
双向验证：仅当两个相邻格子互相“认可”对方方向时，才视为可通行。
BFS遍历：保证按层扩展，最终判断终点是否可达。

复杂度
时间复杂度：O(m × n)，每个格子最多入队一次。
空间复杂度：O(m × n)，用于 vis 数组和队列。