DFS - 980. Unique Paths III

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)

思路：

这是求不同路径的第三个变形题，与62和63题不同的是，对每个方格又增加了状态，1代表起点，2代表终点，0代表可以走，-1代表不可以走，最容易想到的就是使用dfs来求解，往四个方向探索回溯就可以。

代码：

go :

func uniquePathsIII(grid [][]int) int {

    sx := -1
    sy := -1
    n := 1  // 起点算1
    
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == 0 {
                n++
            } else if grid[i][j] == 1 {
                sx = i
                sy = j
            }
        }
    }

    return dfs(grid, sx, sy, n)
}

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

func dfs(grid [][]int, x, y int, n int) int {
    if x < 0 || x == len(grid) || y < 0 || y == len(grid[0]) || grid[x][y] == -1 {
        return 0
    }
    
    // ending
    if grid[x][y] == 2 {
        if n == 0 {
            return 1
        } 
        return 0
    }
    
    var paths int
    
    grid[x][y] = -1
    for _, dic := range dics {
        paths +=  dfs(grid, x + dic[0], y + dic[1], n -1)
    }
    grid[x][y] = 0
    
    return paths
    
}