package main

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	m, n := len(obstacleGrid), len(obstacleGrid[0])
	// only one row/col
	if m == 1 || n == 1 {
		for i := 0; i < m; i++ {
			for j := 0; j < n; j++ {
				if obstacleGrid[i][j] == 1 {
					return 0
				}
			}
		}
		return 1
	}
	grid := make([][]int, m)
	grid[0] = make([]int, n)
	if obstacleGrid[0][0] == 1 {
		return 0
	}
	grid[0][0] = 1
	// first row
	for i := 1; i < n; i++ {
		if obstacleGrid[0][i] == 1 {
			break
		}
		grid[0][i] = 1
	}
	// first col
	for i := 1; i < m; i++ {
		grid[i] = make([]int, n)
		if obstacleGrid[i][0] == 1 {
			grid[i][0] = 0
			continue
		}
		grid[i][0] = grid[i-1][0]
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if obstacleGrid[i][j] == 1 {
				grid[i][j] = 0
			} else {
				grid[i][j] = grid[i-1][j] + grid[i][j-1]
			}
		}
	}
	return grid[m-1][n-1]
}

/* func main() {
	o1 := [][]int{
		{0, 0, 0},
		{0, 1, 0},
		{0, 0, 0},
	}
	fmt.Println(uniquePathsWithObstacles(o1))
	o2 := [][]int{
		{0, 0, 1},
		{0, 0, 0},
		{0, 0, 0},
	}
	fmt.Println(uniquePathsWithObstacles(o2))
} */