吹拉弹唱

var empty int
var res int

func uniquePathsIII(grid [][]int) int {
    // Take account of the ending cell
    empty = 1
    res = 0
    startX, startY := 0, 0
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == 1 {
                startX = i
                startY = j
            } else if grid[i][j] == 0 {
                empty++
            }
        }
    }
    dfs(grid, startX, startY, 0)
    return res
}

func dfs(grid [][]int, x, y int, count int) {
    if x < 0 || y < 0 || x >= len(grid) || y >= len(grid[0]) || grid[x][y] == -1 {
        return
    }
    
    if grid[x][y] == 2 {
        if count == empty {
            res++
        }
        return
    }
    
    // Used as visited
    grid[x][y] = -1
    
    dfs(grid, x-1, y, count+1)
    dfs(grid, x, y-1, count+1)
    dfs(grid, x+1, y, count+1)
    dfs(grid, x, y+1, count+1)
    
    grid[x][y] = 0
    
}