# 1391. Check if There is a Valid Path in a Grid¶

## Information¶

• Diffculty: Medium

• Created: 2020-03-22 15:11:54

• Last Motified: 2020-03-22 15:11:54

• Tags: Depth-first Search, Breadth-first Search

## 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)
if m == n == 1:
return True

for parent in self.STREET[grid]:
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 == parent and y + change == parent:
if x == m - 1 and y == n - 1:
return True
parent = x, y
x, y = x + change, y + change
elif x + change == parent and y + change == parent:
if x == m - 1 and y == n - 1:
return True
parent = x, y
x, y = x + change, y + change
else:
break
return False
```