980.Unique Paths III(不同路径 III)

Description

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.

在二维网格 grid 上，有 4 种类型的方格：

1 表示起始方格。且只有一个起始方格。
2 表示结束方格，且只有一个结束方格。
0 表示我们可以走过的空方格。
-1 表示我们无法跨越的障碍。

返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目，每一个无障碍方格都要通过一次。

题目链接：https://leetcode.com/problems/unique-paths-iii/

Difficulty: hard

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

分析

updating（Solution）

参考代码

class Solution:
def uniquePathsIII(self, grid):
    R, C = len(grid), len(grid[0])

    def neighbors(r, c):
        for nr, nc in ((r-1, c), (r, c-1), (r+1, c), (r, c+1)):
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] % 2 == 0:
                yield nr, nc

    todo = 0
    for r, row in enumerate(grid):
        for c, val in enumerate(row):
            if val != -1: todo += 1
            if val == 1: sr, sc = r, c
            if val == 2: tr, tc = r, c

    self.ans = 0
    def dfs(r, c, todo):
        todo -= 1
        if todo < 0: return
        if r == tr and c == tc:
            if todo == 0:
                self.ans += 1
            return

        grid[r][c] = -1
        for nr, nc in neighbors(r, c):
            dfs(nr, nc, todo)
        grid[r][c] = 0

    dfs(sr, sc, todo)
    return self.ans