63. Unique Paths II 不同路径II

题目

给定一个 m*n 网格 grid。机器人一开始位于 grid[0][0]。机器人想走到grid[m-1][n-1]。机器人每次只能向下或者向右走。
grid 中的 1 代表障碍物，0 代表网格。移动路径上不能包括障碍物。

解析

整体方案参考 Unique Paths。区别在于一旦当前为障碍物，置为 0，否则当前路径值为 grid[i-1][j] + grid[i][j-1]。

伪代码

grid[0][0] = 1
for j:=1;i<m;j++
  if grid[0][j] == 1
    grid[0][j] = 0
  else
    grid[0][j] = grid[0][j-1]

for i:=1;i<n;i++
  if grid[i][0] == 1
    grid[i][0] = 0
  else
    grid[i][0] = grid[i-1][0]

for i:=1;i<m;i++
  for j:=1;j<n;j++
    if grid[i][j] == 1
      grid[i][j] = 0
    else
      grid[i][j] = grid[i][j-1] + grid[i-1][j]
return grid[m-1][n-1]

代码

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    grid:=obstacleGrid
    if grid[0][0] == 1 {
        return 0
    }
    grid[0][0] = 1
    m:=len(grid)
    n:=len(grid[0])
    for i:=1;i<m;i++ {
        if grid[i][0] == 1 {
            grid[i][0] = 0
        }else {
            grid[i][0] = grid[i-1][0]
        }
    }
    for j:=1;j<n;j++ {
        if grid[0][j] == 1 {
            grid[0][j] = 0
        }else {
            grid[0][j] = grid[0][j-1]
        }
    }
    
    for i:=1;i<m;i++ {
        for j:=1;j<n;j++ {
            if grid[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]
}

image.png

后记

1. 测试用例 [[1]] expect 值为 0