# 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[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
```