## DFS - 980. Unique Paths III

Published on with 0 views and 0 comments

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)
``````

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

}
``````