- Notifications
You must be signed in to change notification settings - Fork 625
/
Copy path1091.py
52 lines (39 loc) · 1.62 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
'''
In an N by N square grid, each cell is either empty (0) or blocked (1).
A clear path from top-left to bottom-right has length k if and only if it is composed of cells C_1, C_2, ..., C_k such that:
Adjacent cells C_i and C_{i+1} are connected 8-directionally (ie., they are different and share an edge or corner)
C_1 is at location (0, 0) (ie. has value grid[0][0])
C_k is at location (N-1, N-1) (ie. has value grid[N-1][N-1])
If C_i is located at (r, c), then grid[r][c] is empty (ie. grid[r][c] == 0).
Return the length of the shortest such clear path from top-left to bottom-right. If such a path does not exist, return -1.
Example 1:
Input: [[0,1],[1,0]]
Output: 2
Example 2:
Input: [[0,0,0],[1,1,0],[1,1,0]]
Output: 4
Note:
1 <= grid.length == grid[0].length <= 100
grid[r][c] is 0 or 1
'''
classSolution(object):
defshortestPathBinaryMatrix(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
ifnotgrid:
return-1
rows, cols=len(grid), len(grid[0])
ifgrid[0][0] orgrid[rows-1][cols-1]:
return-1
queue= [[0, 0, 1]]
forrow, col, distinqueue:
ifrow==rows-1andcol==cols-1:
returndist
fordi, djin [(-1, -1), (0, -1), (-1, 1), (-1, 0), (1, 0), (1, -1), (0, 1), (1, 1)]:
n_row, n_col=row+di, col+dj
if0<=n_row<rowsand0<=n_col<colsandnotgrid[n_row][n_col]:
grid[n_row][n_col] =1
queue.append([n_row, n_col, dist+1])
return-1