难度: Hard
原题连接
内容描述
On a 2-dimensional grid, there are 4 types of squares:
1 represents the starting square. There is exactly one starting square.
2 represents the ending square. There is exactly one ending square.
0 represents empty squares we can walk over.
-1 represents obstacles that we cannot walk over.
Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.
Example 1:
Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
Example 2:
Input: [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: We have the following four paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)
Example 3:
Input: [[0,1],[2,0]]
Output: 0
Explanation:
There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.
Note:
1 <= grid.length * grid[0].length <= 20
思路 1 - 时间复杂度: O(4^(row * col))- 空间复杂度: O(row * col)******
暴力dfs
class Solution:
def uniquePathsIII(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
row = len(grid)
col = len(grid[0]) if row else 0
start = []
empty = set()
for i in range(row):
for j in range(col):
if grid[i][j] == 1:
start = [i,j]
elif grid[i][j] == 0:
empty.add((i,j))
self.res = 0
def helper(i, j, cnt, visited):
if (i,j) in visited:
return
if not (0 <= i < row) or not (0 <= j < col) or grid[i][j] == -1:
return
if grid[i][j] == 2:
if cnt == len(empty):
self.res += 1
return
if grid[i][j] == 0:
cnt += 1
visited.add((i,j))
helper(i+1, j, cnt, set(k for k in visited)) # 这里注意一定要重新开一个set，不然会影响后面的visited
helper(i, j+1, cnt, set(k for k in visited))
helper(i, j-1, cnt, set(k for k in visited))
helper(i-1, j, cnt, set(k for k in visited))
helper(start[0], start[1], 0, set())
return self.res思路 2 - 时间复杂度: O(4^(row * col))- 空间复杂度: O(row * col)******
BackTracking DFS，同时用walked来存放我们已经走过多少步了，避免了思路一中visited可能带来的问题
class Solution:
def uniquePathsIII(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
row = len(grid)
col = len(grid[0]) if row else 0
start, walks = [], 0
for i in range(row):
for j in range(col):
if grid[i][j] == 0:
walks += 1
elif grid[i][j] == 1:
start = [i,j]
nexts = [[0,1], [0,-1], [1,0], [-1,0]]
self.res = 0
def dfs(i, j, walked):
if not (0 <= i < row) or not (0 <= j < col) or grid[i][j] < 0:
return
if grid[i][j] == 2 and walked == walks + 1:
self.res += 1
return
val = grid[i][j]
grid[i][j] = -2
for nxt in nexts:
dfs(i + nxt[0], j + nxt[1], walked + 1)
grid[i][j] = val
dfs(start[0], start[1], 0)
return self.res