Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
 一个row行col列的二维矩阵,初始所有元素为0,代表均可以走,每天有一个格子变为1,不可走,问最迟第几天可以依旧从第一行走到最后一行(具体从第几列开始,走向第几列无要求),可以四个方向走
二分答案+DFS确认是否可达


 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 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理