Leetcode 980 Unique Paths III

发表于 |

给定一个二维矩阵grid，里面包含4种不同的块：
1代表起始位置，确保矩阵里只有一个起始位置
2代表终点位置，确保矩阵里只有一个终点位置
0代表空白，可以在空白路径上移动
-1代表障碍，不可以再障碍物处移动

返回从起始位置出发，依次走遍所有的空白位置（恰好一次），最后到达终点的不同路径数。

示例 1：
输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
输出: 2
解释: 共有两种方式:

  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)
    示例 2:
    输入: [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
    输出: 4
    解释：共有四种方式:
  3. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
  4. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
  5. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
  6. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)
    示例 3:
    输入: [[0,1],[2,0]]
    输出: 0
    解释: 没有任何路径

注意起始位置和终点位置可能在矩阵的任意一个地方.

提示:

  1. 1 <= grid.length * grid[0].length <= 20

思路分析：
这和旅行商问题有异曲同工之妙，对旅行商问题有兴趣的可以参考这道题

关键点就是在于如何表示已经行走过的路径，这道题提示中说总格子数不超过20，那么用一个20空间大小的bool数组来表示可以吗？
未必不行，但没有必要。希望大家对这种题目敏感一点，用01代表状态的时候，要能反映过来可以用位。20位整数一个int型变量就可以保存，每一位上1代表已经走过，0代表还没走过。

然后判断处终点情况的位表示情况，例如对于示例2中的网格，终点情况应该是011111111111，因为最后一个数是-1，所以不能到达，故位表示的首位是0。依次类推，将起点的位表示计算出来，然后dfs遍历。

当然，如果你做了旅行商那道题的话，你应该知道其实这里面是包含重复计算的，我们应该使用记忆化的思想去递归。想知道为何有重复计算可以参考这篇博客。

懒得看也没关系，看下面的代码也ok。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
    def uniquePathsIII(self, grid):
        n,m = len(grid), len(grid[0])
        start = 0
        final = 0
        fi = fj = 0
        # 先获得起始位置和终点位置，以及起始和终点的位表示
        for i in range(n):
            for j in range(m):
                if grid[i][j] != -1:
                    final += 1 << (i*m+j)
                if grid[i][j] == 1:
                    start += 1 << (i*m+j)
                    si, sj = i, j
                if grid[i][j] == 2:
                    fi, fj = i, j

        # 使用记忆化思想，存储已经走过的情况
        cache = {(start,si,sj): 1}
        def solve(status, i, j):
            if (status,i,j) in cache: return cache[status,i,j]
            res = 0
            now_status = 1 << (i*m + j)
            # 每次向四个临近结点移动，但要保证临近结点能走
            for x,y in [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]:
                if 0<=x<n and 0<=y<m and grid[x][y] != -1:
                    # 保证每个空白位置只走一遍
                    mask = 1 << (x*m+y)
                    if status & mask:
                        res += solve(status ^ now_status, x, y)
            cache[status,i,j] = res
            return res
        return solve(final, fi, fj)

# 39 / 39 test cases passed.
# difficulty: hard
# Runtime: 64 ms