Topic describes

A robot is located in the upper left corner of an M x N grid (the starting point is marked “Start” in the figure below). The robot can only move one step to the right or down at a time. The robot attempts to reach the lower right corner of the grid (marked “Finish” in the image below). Now consider that there are obstacles in the grid. So how many different paths are there going to be from the top left to the bottom right?

Obstacles and empty positions in the grid are represented by 1 and 0 respectively.

** Note: ** the value of m and n cannot exceed 100.

Example 1

Input: [[0, 0], [0, 0] to [0, 0]] output: 2:3 x3 grid right in the middle there is a barrier. There are two different paths from the upper left corner to the lower right corner: 1. Right -> Right -> Down -> Down 2. Down -> down -> right -> rightCopy the code

Answer key

package main

import (
	"fmt"
)

func main(a) {
	grid := [][]int{{0.0.0}, {0.1.0}, {0.0.0}}
	len := uniquePathsWithObstacles(grid)
	fmt.Println(len)}func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	n, m := len(obstacleGrid), len(obstacleGrid[0])
	f := make([]int, m)
	if obstacleGrid[0] [0] = =0 {
		f[0] = 1
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if obstacleGrid[i][j] == 1 {
				f[j] = 0
				continue
			}
			if j- 1> =0 && obstacleGrid[i][j- 1] = =0 {
				f[j] += f[j- 1]}}}return f[len(f)- 1]}Copy the code