Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一个迷宫图,格点值-1,0,1,2分别表示障碍、可走的格子、起点、终点,问起点到终点经过所有可走格子的路径有几条

写了个裸DFS,效率一般

另有基于位运算和DP的解法,可以参考->https://leetcode.com/problems/unique-paths-iii/solutions/222466/python-bit-mask-dp-solution/

 1 #980
 2 #Runtime: 78 ms (Beats 54.24%)
 3 #Memory: 13.6 MB (Beats 23.73%)
 4 
 5 class Solution(object):
 6     def uniquePathsIII(self, grid):
 7         """
 8         :type grid: List[List[int]]
 9         :rtype: int
10         """
11         d = [[-1, 0], [1, 0], [0, 1], [0, -1]]
12         m, n = len(grid), len(grid[0])
13         self.ans = 0
14 
15         def DFS(x, y, vis, nonempty):
16             if grid[x][y] == 2 and nonempty == -1:
17                 self.ans += 1
18                 return
19             vis.add((x, y))
20             for tx, ty in d:
21                 if (x + tx, y + ty) not in vis and x + tx in range(m) and y + ty in range(n) and grid[x + tx][y + ty] != -1:
22                     DFS(x + tx, y + ty, vis, nonempty - 1)
23                     #vis[x + tx][y + ty] = 0
24             vis.remove((x, y))
25 
26         nonempty = 0
27         for x in range(len(grid)):
28             for y in range(len(grid[0])):
29                 if grid[x][y] == 1:
30                     st_x, st_y = x, y
31                 elif grid[x][y] == 0:
32                     nonempty += 1
33         DFS(st_x, st_y, set(), nonempty)
34         return self.ans







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