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

难度: 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) 。

示例 4：

输入：grid = [[1,1,1,1,1,1,3]]
输出：true

示例 5：

输入：grid = [[2],[2],[2],[2],[2],[2],[6]]
输出：true

提示：

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

Submission

运行时间: 92 ms

内存: 20.2 MB

dir4 = [(1, 0), (0, 1), (-1, 0), (0, -1)]
mp = [[],
    [-1, 1, -1, 3], 
    [0, -1, 2, -1], 
    [-1, 0, 3, -1], 
    [-1, -1, 1, 0],
    [3, 2, -1, -1],
    [1, -1, -1, 2]]

class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        vis = [[False] * n for _ in range(m)]
        def travel(d0):
            r, c = 0, 0
            vis[0][0] = False
            d = d0
            while True:
                if r < 0 or r >= m or c < 0 or c >= n or vis[r][c]:
                    return False
                vis[r][c] = True
                d = mp[grid[r][c]][d]
                if d == -1:
                    return False
                if r == m-1 and c == n-1:
                    return True
                dr, dc = dir4[d]
                r += dr
                c += dc
        return any(travel(d) for d in range(4))

Explain

这个题解采用的是基于方向的模拟遍历方法。首先定义了四个基本的前进方向和一个映射表mp。映射表mp用于指示每个类型的街道如何改变当前的方向。我们从网格的左上角开始，尝试沿每个可能的初始方向进行遍历。在遍历的过程中，我们检查是否越界或者是否重复访问同一个单元格，若是，则此路径无效。如果到达右下角，则返回true表示存在有效路径。如果所有的可能初始方向都无法到达目的地，则返回false。

时间复杂度: O(m*n)

空间复杂度: O(m*n)

dir4 = [(1, 0), (0, 1), (-1, 0), (0, -1)] # 定义四个基本的前进方向：下，右，上，左
mp = [[],
    [-1, 1, -1, 3],
    [0, -1, 2, -1],
    [-1, 0, 3, -1],
    [-1, -1, 1, 0],
    [3, 2, -1, -1],
    [1, -1, -1, 2]] # 映射表，指示各类型街道如何改变方向
class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        m, n = len(grid), len(grid[0]) # 网格的行数和列数
        vis = [[False] * n for _ in range(m)] # 访问标记数组
        def travel(d0):
            r, c = 0, 0 # 起始位置
            vis[0][0] = False
            d = d0 # 初始方向
            while True:
                if r < 0 or r >= m or c < 0 or c >= n or vis[r][c]: # 检查是否越界或者重复访问
                    return False
                vis[r][c] = True # 标记当前单元格为已访问
                d = mp[grid[r][c]][d] # 根据当前单元格类型和当前方向决定下一个方向
                if d == -1: # 如果没有有效的下一个方向
                    return False
                if r == m-1 and c == n-1: # 如果到达右下角
                    return True
                dr, dc = dir4[d] # 获取方向向量
                r += dr # 更新行坐标
                c += dc # 更新列坐标
        return any(travel(d) for d in range(4)) # 从所有四个方向尝试，如果任一方向成功则返回true

Explore

在映射表`mp`中，-1表示当前街道类型不支持进入此方向。例如，如果在某个方向上的映射结果是-1，意味着从当前单元格的这种街道类型不能转向该方向，因此这条路径在这个方向上是封闭的，不能通过。这是一种错误检测或者边界处理的机制，用于防止路径走向无效的方向。

这里的描述应该是一个错误。理论上，`vis`数组应该在每次调用`travel`函数时都被重置，以防止从不同起始方向开始的路径错误地共享访问状态。每次开始新的路径探索前，应清空或重置`vis`数组，确保每个路径探索都是独立的。如果不这么做，可能会导致算法错误地判断某些路径是不可达的，因为它们可能受到之前路径尝试的影响。

原题解中没有直接体现确保两个相邻单元格街道之间的连接性。实际上，这是算法正确性的关键一环。在每次移动到新单元格后，应该检查新单元格的街道类型是否允许从前一个单元格的方向进入。如果不进行这样的检查，可能会出现路径实际上是不连通的情况，但算法错误地认为这些路径是有效的。

四个基本方向代表了二维网格中可以移动的全部方向：向下（1,0）、向右（0,1）、向上（-1,0）和向左（0,-1）。这些方向覆盖了从任一单元格可能的移动方向，确保可以全面探索网格。在具体实现中，算法尝试从网格的起始位置（左上角）分别向这四个方向探索，以确定是否存在至少一个方向能够通过符合街道连接规则的路径到达网格的终点（右下角）。这种方法确保了算法能从所有可能的初始方向进行路径搜索。