980. 不同路径 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)
- 1. (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
解释：我们有以下四条路径：
- 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)
- 1. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
- 1. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
- 1. (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 <= grid.length * grid[0].length <= 20

解法一：回溯

 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


func uniquePathsIII(grid [][]int) int {
    h, w := len(grid), len(grid[0])
    zeros, si, sj := 0, 0, 0
    for i := 0; i < h; i++ {
        for j := 0; j < w; j++ {
            if grid[i][j] == 0 {
                zeros++
            } else if grid[i][j] == 1 {
                zeros++
                si = i
                sj = j
            }
        }
    }

    dirs := [][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
    var dfs func(i, j, n int) int
    dfs = func(i, j, n int) int {
        if grid[i][j] == 2 {
            if 0 == n {
                return 1
            }
            return 0
        }
        count, rawVal := 0, grid[i][j]
        grid[i][j] = -1
        for _, dir := range dirs {
            ni, nj := i+dir[0], j+dir[1]
            if 0 <= ni && ni < h && 0 <= nj && nj < w && (grid[ni][nj] == 0 || grid[ni][nj] == 2) {
                count += dfs(ni, nj, n-1)
            }
        }
        grid[i][j] = rawVal
        return count
    }
    return dfs(si, sj, zeros)
}