一個(gè)row行col列的二維矩陣，初始所有元素為0，代表均可以走，每天有一個(gè)格子變?yōu)?，不可走，問最遲第幾天可以依舊從第一行走到最后一行（具體從第幾列開始，走向第幾列無要求），可以四個(gè)方向走
二分答案+DFS確認(rèn)是否可達(dá)
1 #1970
2 #Runtime: 3361 ms (Beats 85.71%)
3 #Memory: 39.9 MB (Beats 14.29%)
4
5 class Solution(object):
6 def latestDayToCross(self, row, col, cells):
7 """
8 :type row: int
9 :type col: int
10 :type cells: List[List[int]]
11 :rtype: int
12 """
13 d = [[0, 1], [0, -1], [-1, 0], [1, 0]]
14 def DFS(grid, r, c):
15 if 0 <= r < row and 0 <= c < col and grid[r][c] == 0:
16 if r == row - 1:
17 return True
18 grid[r][c] = -1
19 for x in d:
20 tr = r + x[0]
21 tc = c + x[1]
22 if DFS(grid, tr, tc):
23 return True
24 return False
25
26 def ok(x):
27 grid = [[0] * col for _ in range(row)]
28 for i in range(x):
29 grid[cells[i][0] - 1][cells[i][1] - 1] = 1
30 for i in range(col):
31 if grid[0][i] == 0 and DFS(grid, 0, i):
32 return True
33 return False
34
35 l = 1
36 r = len(cells)
37 while l < r:
38 mid = (l + r) // 2 + (l + r) % 2
39 if ok(mid):
40 l = mid
41 else:
42 r = mid - 1
43 return l
44