Check if There is a Valid Path in a Grid

Intuition

For each Street, there could be at most 2 ways about how to use it. And if its parent is sure, there is only one way about how to use it.

So we could solve the problem by following way.

Solution


class Solution:
    STREET = {
        1: [(0, -1), (0, 1)],
        2: [(-1, 0), (1, 0)],
        3: [(0, -1), (1, 0)],
        4: [(1, 0), (0, 1)],
        5: [(0, -1), (-1, 0)],
        6: [(-1, 0), (0, 1)]
    }

    def hasValidPath(self, grid: List[List[int]]) -> bool:
        m = len(grid)
        n = len(grid[0])
        if m == n == 1:
            return True

        for parent in self.STREET[grid[0][0]]:
            x, y = 0, 0
            while True:
                if x < 0 or y < 0 or x >= m or y >= n:
                    break
                change = self.STREET[grid[x][y]]
                if x + change[0][0] == parent[0] and y + change[0][1] == parent[1]:
                    if x == m - 1 and y == n - 1:
                        return True
                    parent = x, y
                    x, y = x + change[1][0], y + change[1][1]
                elif x + change[1][0] == parent[0] and y + change[1][1] == parent[1]:
                    if x == m - 1 and y == n - 1:
                        return True
                    parent = x, y
                    x, y = x + change[0][0], y + change[0][1]
                else:
                    break
        return False