980. Unique Paths III #

Problem #

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

Problem Summary #

On a 2D 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 cross.

Return the number of different paths in the four directions (up, down, left, and right) from the starting square to the ending square, where every non-obstacle square must be walked over exactly once.

Solution Approach #

• This problem can also be solved according to the approach of Problem 79. The problem asks us to output the number of paths from the start point to the end point in the map. Note that the path must cover all blank squares.
• The only thing to note is that the blank squares are not the final total number of steps: total steps = number of blank squares + 1, because we need to walk to the end point, and reaching the end point also counts as one step.

Code #

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) // Add one to the number of steps that can be taken, because the ending square also counts as one step; otherwise we can never reach the end!
	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++ Although this variable's value could be restored here, the assignment is meaningless, so just leave it out
		path = path[:len(path)-2]
	}
	return
}