給出一個(gè)迷宮圖，格點(diǎn)值-1，0，1，2分別表示障礙、可走的格子、起點(diǎn)、終點(diǎn)，問起點(diǎn)到終點(diǎn)經(jīng)過所有可走格子的路徑有幾條
寫了個(gè)裸DFS，效率一般
另有基于位運(yùn)算和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