forked from yanglei-github/Leetcode_in_python3
-
Notifications
You must be signed in to change notification settings - Fork 0
/
1091_二进制矩阵中的最短路径.py
139 lines (126 loc) · 5.41 KB
/
1091_二进制矩阵中的最短路径.py
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 7 16:20:42 2020
@author: leiya
"""
'''
类比树，每次拿出树的一层，然后一个一个拿出这层中的所有node，判断每个node的下一个node是否可以
正好probe下探到结束点，同时将符合通道要求但是没有触及到结束点的该层的下一层node放到下一层统一的list中
如果这层所有的node全部找完了，但是所有的node的下一层node没有到结束点，那么我们进行下一层遍历。
总体上来说，每轮循环遍历树的一层node，因为这层node是上一层可以走到的node，走到这一层node需要的距离一样，这样
一层一层的找，知道找到一层中的某个node的bfs中的下一层node恰好是结束点，这个时候就可以结束了
Note:值得注意的就是，该层符合通道要求的下一层node找到后应该置为-1，这样该层中其他node找到这个node的时候就不用在记录了，
同时也保证了下一层node的bfs循环的时候找到该节点时不会记录，因为该节点明显可以在上一层抵达，在这层再去抵达没有意义，因为一定会造成路径的浪费
'''
#0625 updated:
#注意这是方形网格，row=col，注意特殊情况的处理
class Solution:
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
row = len(grid)
col = len(grid[0])
if row == 1 and grid[0][0] == 0:
return 1
if grid[0][0] == 1 or grid[-1][-1] == 1:
return -1
queue = [(0,0)]
count = 1
while queue:
current_len = len(queue)
for i in range(current_len):
tempx,tempy = queue.pop(0)
for x,y in [(0,1),(0,-1),(1,-1),(1,0),(1,1),(-1,0),(-1,-1),(-1,1)]:
curx = tempx + x
cury = tempy + y
if 0 <= curx < row and 0 <= cury < col and grid[curx][cury] == 0:
if curx == row - 1 and cury == col - 1:
return count + 1
grid[curx][cury] = 1
queue.append((curx,cury))
count += 1
return -1
class Solution:
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
n = len(grid)
if n == 1 and grid[0][0] == 0:
return 1
if grid[0][0] == 1 or grid[-1][-1] == 1:
return -1
grid[0][0] = -1
res = 1
cur_queue = [(0,0)]
while cur_queue:
next_queue = []
for i,j in cur_queue:
for x, y in [(-1,0),(-1,-1),(0,1),(0,-1),(1,1),(1,0),(1,-1),(-1,1)]:
temp_i = i + x
temp_j = j + y
if temp_i == n-1 and temp_j == n-1:
return res + 1
if not 0 <= temp_i < n or not 0 <= temp_j < n:
continue
if grid[temp_i][temp_j] == 1:
continue
if grid[temp_i][temp_j] == -1:
continue
if grid[temp_i][temp_j] == 0:
grid[temp_i][temp_j] = -1
next_queue.append((temp_i,temp_j))
cur_queue = next_queue
res += 1
return -1
class Solution:
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
n = len(grid)
if n == 1 and grid[0][0] == 0:
return 1
if grid[0][0] == 1 or grid[-1][-1] == 1:
return -1
grid[0][0] = 1
res = 1
cur_queue = [(0,0)]
while cur_queue:
next_queue = []
for i,j in cur_queue:
for x, y in [(-1,0),(-1,-1),(0,1),(0,-1),(1,1),(1,0),(1,-1),(-1,1)]:
temp_i = i + x
temp_j = j + y
if temp_i == n-1 and temp_j == n-1:
return res + 1
if not 0 <= temp_i < n or not 0 <= temp_j < n:
continue
if grid[temp_i][temp_j] == 1:
continue
if grid[temp_i][temp_j] == 0:
grid[temp_i][temp_j] = 1
next_queue.append((temp_i,temp_j))
cur_queue = next_queue
res += 1
return -1
class Solution:
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
n = len(grid)
if n == 1 and grid[0][0] == 0:
return 1
if grid[0][0] == 1 or grid[-1][-1] == 1:
return -1
grid[0][0] = 1
res = 1
queue = [(0,0)]
while queue:
current_len = len(queue)
for i in range(current_len):
a,b = queue.pop(0)
for x, y in [(-1,0),(-1,-1),(0,1),(0,-1),(1,1),(1,0),(1,-1),(-1,1)]:
temp_i = a + x
temp_j = b + y
if temp_i == n-1 and temp_j == n-1:
return res + 1
if not 0 <= temp_i < n or not 0 <= temp_j < n:
continue
if grid[temp_i][temp_j] == 1:
continue
if grid[temp_i][temp_j] == 0:
grid[temp_i][temp_j] = 1
queue.append((temp_i,temp_j))
res += 1
return -1