Leetcode 1391：检查网格中是否存在有效路径（超详细的解法！！！）

给你一个 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

解题思路

首先比较容易想到的做法就是将原先的街道通过9*9的像素格表示，这样我们就变了判断两个红点之间是不是存在路径的问题了。

class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        r, c = len(grid), len(grid[0])
        nr, nc = 3 * r, 3 * c
        g = [[0] * nc for _ in range(nr)]
        d = [0, 1, 0, -1, 0]
        
        for i in range(r):
            for j in range(c):
                r = grid[i][j]
                g[i * 3 + 1][j * 3 + 1] = True
                g[i * 3 + 1][j * 3 + 0] = r == 1 or r == 3 or r == 5
                g[i * 3 + 1][j * 3 + 2] = r == 1 or r == 4 or r == 6
                g[i * 3 + 0][j * 3 + 1] = r == 2 or r == 5 or r == 6
                g[i * 3 + 2][j * 3 + 1] = r == 2 or r == 3 or r == 4
                
        def dfs(x, y):
            if x == nr - 2 and y == nc - 2: return True
            
            res = False
            for i in range(4):
                nx, ny = x + d[i], y + d[i + 1]
                if 0 <= nx < nr and 0 <= ny < nc and g[nx][ny] == True:
                    g[nx][ny] = False
                    res |= dfs(nx, ny)
            return res
        
        return dfs(1, 1)

但是这么做超时了。

对于每个街道，它的上一个可能来自四个方向，首先我们通过数组定义这四个方向[右，下，左，上]。然后针对每个街道，判断这四个方向哪些方向是联通的，对于联通的方向用1表示。

1 : [1, 0, 1, 0]
2 : [0, 1, 0, 1]
3 : [0, 1, 1, 0]
4 : [1, 1, 0, 0]
5 : [0, 0, 1, 1]
6 : [1, 0, 0, 1]

还需注意一点，前一个街道要和后一个街道联通，并且前一个街道的方向正好和后一个街道相反，也就是1对应3，而0对应2，所以可以通过异或2得到相反的方向。

class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        r, c = len(grid), len(grid[0])
        d = [0, 1, 0, -1, 0]
        p = [[1, 0, 1, 0], 
            [0, 1, 0, 1], 
            [0, 1, 1, 0],
            [1, 1, 0, 0],
            [0, 0, 1, 1],
            [1, 0, 0, 1]]
        
        def dfs(x, y):
            if x == r - 1 and y == c - 1: return True

            k, grid[x][y] = grid[x][y], 0
            for i in range(4):
                nx, ny = x + d[i], y + d[i + 1]
                if 0 <= nx < r and 0 <= ny < c and grid[nx][ny] and \
                    p[k - 1][i] and p[grid[nx][ny] - 1][i ^ 2]: # 判断前一个街道和后一个街道是否联通
                    if dfs(nx, ny): return True
            return False
        return dfs(0, 0)

上面这个代码也非常容易写出bfs版本。

class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        r, c = len(grid), len(grid[0])
        d = [0, 1, 0, -1, 0]
        p = [[1, 0, 1, 0], 
            [0, 1, 0, 1], 
            [0, 1, 1, 0],
            [1, 1, 0, 0],
            [0, 0, 1, 1],
            [1, 0, 0, 1]]
        
        q = [[0, 0]]
        while q:
            x, y = q.pop(0)
            if x == r - 1 and y == c - 1: return True

            k, grid[x][y] = grid[x][y], 0
            for i in range(4):
                nx, ny = x + d[i], y + d[i + 1]
                if 0 <= nx < r and 0 <= ny < c and grid[nx][ny] and \
                    p[k - 1][i] and p[grid[nx][ny] - 1][i ^ 2]: # 判断前一个街道和后一个街道是否联通
                    q.append([nx, ny])
        return False

reference:

https://leetcode.com/problems/check-if-there-is-a-valid-path-in-a-grid/discuss/547225/C%2B%2B-with-picture%3A-track-direction-%2B-DFS-on-upscaled-grid

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题，希望大家指出！！！

「如果我的文章对你有很大帮助，那么不妨～！」