1507 Check If There Is A Valid Path In A Grid
1507 Check If There Is A Valid Path In A Grid
Check if There is a Valid Path in a Grid 
You are given an m x n grid. Each cell of grid represents a street. The street of grid[i][j] can be:
1
2
3
4
5
6
1 which means a street connecting the left cell and the right cell.
2 which means a street connecting the upper cell and the lower cell.
3 which means a street connecting the left cell and the lower cell.
4 which means a street connecting the right cell and the lower cell.
5 which means a street connecting the left cell and the upper cell.
6 which means a street connecting the right cell and the upper cell.
You will initially start at the street of the upper-left cell (0, 0). A valid path in the grid is a path that starts from the upper left cell (0, 0) and ends at the bottom-right cell (m - 1, n - 1). The path should only follow the streets.
Notice that you are not allowed to change any street.
Return true* if there is a valid path in the grid or false otherwise*.
Example 1:
1
2
3
4
5
**Input:** grid = [[2,4,3],[6,5,2]]
**Output:** true
**Explanation:** As shown you can start at cell (0, 0) and visit all the cells of the grid to reach (m - 1, n - 1).
Example 2:
1
2
3
4
5
**Input:** grid = [[1,2,1],[1,2,1]]
**Output:** false
**Explanation:** As shown you the street at cell (0, 0) is not connected with any street of any other cell and you will get stuck at cell (0, 0)
Example 3:
1
2
3
4
5
**Input:** grid = [[1,1,2]]
**Output:** false
**Explanation:** You will get stuck at cell (0, 1) and you cannot reach cell (0, 2).
Constraints:
1
2
3
4
m == grid.length
n == grid[i].length
1 <= m, n <= 300
1 <= grid[i][j] <= 6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution:
class DisjointSet:
def __init__(self, n):
self.f = list(range(n))
def find(self, x):
if x == self.f[x]:
return x
self.f[x] = self.find(self.f[x])
return self.f[x]
def merge(self, x, y):
self.f[self.find(x)] = self.find(y)
def hasValidPath(self, grid: List[List[int]]) -> bool:
m, n = len(grid), len(grid[0])
ds = Solution.DisjointSet(m * n)
def getId(x, y):
return x * n + y
def detectL(x, y):
if y - 1 >= 0 and grid[x][y - 1] in [1, 4, 6]:
ds.merge(getId(x, y), getId(x, y - 1))
def detectR(x, y):
if y + 1 < n and grid[x][y + 1] in [1, 3, 5]:
ds.merge(getId(x, y), getId(x, y + 1))
def detectU(x, y):
if x - 1 >= 0 and grid[x - 1][y] in [2, 3, 4]:
ds.merge(getId(x, y), getId(x - 1, y))
def detectD(x, y):
if x + 1 < m and grid[x + 1][y] in [2, 5, 6]:
ds.merge(getId(x, y), getId(x + 1, y))
def handler(x, y):
if grid[x][y] == 1:
detectL(x, y)
detectR(x, y)
elif grid[x][y] == 2:
detectU(x, y)
detectD(x, y)
elif grid[x][y] == 3:
detectL(x, y)
detectD(x, y)
elif grid[x][y] == 4:
detectR(x, y)
detectD(x, y)
elif grid[x][y] == 5:
detectL(x, y)
detectU(x, y)
else:
detectR(x, y)
detectU(x, y)
for i in range(m):
for j in range(n):
handler(i, j)
return ds.find(getId(0, 0)) == ds.find(getId(m - 1, n - 1))
This post is licensed under CC BY 4.0 by the author.