golang刷leetcode：到达角落需要移除障碍物的最小数目

给你一个下标从 0 开始的二维整数数组 grid ，数组大小为 m x n 。每个单元格都是两个值之一：

0 表示一个 空 单元格，

1 表示一个可以移除的 障碍物 。

你可以向上、下、左、右移动，从一个空单元格移动到另一个空单元格。

现在你需要从左上角 (0, 0) 移动到右下角 (m - 1, n - 1) ，返回需要移除的障碍物的 最小 数目。

示例 1：

输入：grid = [[0,1,1],[1,1,0],[1,1,0]]

输出：2

解释：可以移除位于 (0, 1) 和 (0, 2) 的障碍物来创建从 (0, 0) 到 (2, 2) 的路径。

可以证明我们至少需要移除两个障碍物，所以返回 2 。

注意，可能存在其他方式来移除 2 个障碍物，创建出可行的路径。

示例 2：

输入：grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]

输出：0

解释：不移除任何障碍物就能从 (0, 0) 到 (2, 4) ，所以返回 0 。

提示：

m == grid.length

n == grid[i].length

1 <= m, n <= 105

2 <= m * n <= 105

grid[i][j] 为 0 或 1

grid[0][0] == grid[m - 1][n - 1] == 0

解题思路：

1，由于本题有后效性，从上下左右四个方向都可以到达某个节点，所以无法使用动态规划

2，本题其实是起点到终点的最短路径问题，位置为0的地方我们认为路径的最大代价是0，有障碍物的地方代价是1

3，是一个简化版本的dijstra算法

A，我们到达任意节点最多m*n步，可以作为最大路径长度初始化我们的图

B，从起始点出发，我们将距离为0的点的距离该为0，为1的点的距离改成1

C，优先从距离最短的点往周围扩算，即距离为0的点，如果没有距离为0的点，我们可以考虑距离为1的点

D，维护优先队列太麻烦了，本题可以简化成两个数组，数组0是通过距离为0的路径到达的，数组1是经过距离为1的点到达的，每到达一个点加入到对应数组末尾。

E，两个数组一定是递增的

F，所以我们优先取距离最小的，也就是从数组0开始取，由于数组0具有特殊性，都是0，从数组头还是尾取都是一样的，但是数组1，必须从头取

代码实现：

func minimumObstacles(grid [][]int) (ans int) {
   m,n:=len(grid),len(grid[0])
   path:=make([][]int,m)
   for i:=0;i<m;i++{
       path[i]=make([]int,n)
       for j:=0;j<n;j++{
           path[i][j]=m*n
       }
   }
   path[0][0]=0
  
  dir:=[]pos{{-1,0},{1,0},{0,-1},{0,1}}

   var q0,q1 []pos
   q0=append(q0,pos{})
   for len(q0)>0 ||len(q1)>0{
       var p pos
       if len(q0)>0{
          p=q0[len(q0)-1]
          q0=q0[:len(q0)-1]
       }else{
          p=q1[0]
          q1=q1[1:]
       }
       for _,d:=range dir{
            p1:=pos{}
           p1.x=p.x+d.x
           p1.y=p.y+d.y
           if p1.x>=0&&p1.x<m && p1.y>=0&&p1.y<n{
               if grid[p1.x][p1.y]==1{
                    if path[p1.x][p1.y]>path[p.x][p.y]+1{
                        path[p1.x][p1.y]=path[p.x][p.y]+1
                         q1=append(q1,p1)
                    }
               }else{
                    if path[p1.x][p1.y]>path[p.x][p.y]{
                        path[p1.x][p1.y]=path[p.x][p.y]
                        q0=append(q0,p1)
                    }
               }
           }
       }
   }
   return path[m-1][n-1]
}

type pos struct {
    x,y int
}

复制