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.
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