0980. Unique Paths I I I

# 980. Unique Paths III#

## 题目 #

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. `1 <= grid.length * grid[0].length <= 20`

## 题目大意 #

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

## 解题思路 #

• 这一题也可以按照第 79 题的思路来做。题目要求输出地图中从起点到终点的路径条数。注意路径要求必须走满所有空白的格子。
• 唯一需要注意的一点是，空白的格子并不是最后走的总步数，`总步数 = 空白格子数 + 1`，因为要走到终点，走到终点也算一步。

## 代码 #

``````
package leetcode

var dir = [][]int{
{-1, 0},
{0, 1},
{1, 0},
{0, -1},
}

func uniquePathsIII(grid [][]int) int {
visited := make([][]bool, len(grid))
for i := 0; i < len(visited); i++ {
visited[i] = make([]bool, len(grid[0]))
}
res, empty, startx, starty, endx, endy, path := 0, 0, 0, 0, 0, 0, []int{}
for i, v := range grid {
for j, vv := range v {
switch vv {
case 0:
empty++
case 1:
startx, starty = i, j
case 2:
endx, endy = i, j
}
}
}
findUniquePathIII(grid, visited, path, empty+1, startx, starty, endx, endy, &res) // 可走的步数要加一，因为终点格子也算一步，不然永远走不到终点！
return res
}

func isInPath(board [][]int, x, y int) bool {
return x >= 0 && x < len(board) && y >= 0 && y < len(board[0])
}

func findUniquePathIII(board [][]int, visited [][]bool, path []int, empty, startx, starty, endx, endy int, res *int) {
if startx == endx && starty == endy {
if empty == 0 {
*res++
}
return
}
if board[startx][starty] >= 0 {
visited[startx][starty] = true
empty--
path = append(path, startx)
path = append(path, starty)
for i := 0; i < 4; i++ {
nx := startx + dir[i][0]
ny := starty + dir[i][1]
if isInPath(board, nx, ny) && !visited[nx][ny] {
findUniquePathIII(board, visited, path, empty, nx, ny, endx, endy, res)
}
}
visited[startx][starty] = false
//empty++ 这里虽然可以还原这个变量值，但是赋值没有意义，干脆不写了
path = path[:len(path)-2]
}
return
}

``````

Apr 8, 2023