-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCheck if There is a Valid Path in a Grid
More file actions
44 lines (35 loc) · 1.58 KB
/
Copy pathCheck if There is a Valid Path in a Grid
File metadata and controls
44 lines (35 loc) · 1.58 KB
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
class Solution:
def hasValidPath(self, grid: List[List[int]]) -> bool:
left = {i: {1,4,6} for i in [1,3,5]}
right = {i:[1,3,5] for i in [1,4,6]}
up = {i:[2,3,4] for i in [2,5,6]}
down = {i:[2,5,6] for i in [2,3,4] }
cols= len(grid[0])
rows= len(grid)
rep = {}
for row in range(rows):
for col in range(cols):
rep[(row,col)] = (row,col)
def find(node):
if rep[node] != node:
rep[node] = find(rep[node])
return rep[node]
def union(x, y):
xrep = find(x)
yrep = find(y)
if xrep!=yrep:
rep[yrep] = xrep
dirr = {}
for row in range(rows):
for col in range(cols):
if row == 0 and col == 0:
continue
if row + 1 < rows and grid[row][col] in down and grid[row + 1][col] in down[grid[row][col]]:
union((row,col),(row+1,col))
if row -1 >= 0 and grid[row][col] in up and grid[row - 1][col] in up[grid[row][col]]:
union((row,col),(row-1,col))
if col + 1 < cols and grid[row][col] in right and grid[row][col+1] in right[grid[row][col]]:
union((row,col),(row,col+1))
if col - 1 >=0 and grid[row][col] in left and grid[row][col-1] in left[grid[row][col]]:
union((row,col),(row,col-1))
return find((rows-1,cols-1)) == find((0,0))