title
给你一个下标从 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.lengthn == grid[i].length1 <= m, n <= 1052 <= m * n <= 105grid[i][j]为0或1grid[0][0] == grid[m - 1][n - 1] == 0
solution
dijstra 优先队列做法，保存每个点的最少cost
class Directions:
dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
diagonal_dirs = [(1, 1), (1, -1), (-1, 1), (-1, -1)]
all_dirs = dirs + diagonal_dirs
class Solution:
def minimumObstacles(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
if m == 1 and n == 1:
return 0
heap = [(0, (0, 0))]
if grid[0][0] == 1:
heap = [(1, (0, 0))]
dist = {}
import heapq
while heap:
(cost, u) = heapq.heappop(heap)
if u in dist:
continue
dist[u] = cost
x, y = u
if x == m - 1 and y == n - 1:
return cost
for dx, dy in Directions.dirs:
nx, ny = x + dx, y + dy
if nx < 0 or nx >= m or ny < 0 or ny >= n:
continue
v = (nx, ny)
if v in dist:
continue
if grid[nx][ny] == 1:
heapq.heappush(heap, (cost + 1, v))
else:
heapq.heappush(heap, (cost, v))
return -1
01 bfs做法，最先pop的是cost最低的
class Solution:
def minimumObstacles(self, grid: List[List[int]]) -> int:
'''
dijstra, pop时已经是最短成本了，以成本作为优先策略
:param grid:
:return:
'''
m, n = len(grid), len(grid[0])
if m == 1 and n == 1:
return 0
q = collections.deque()
if grid[0][0] == 1:
q.append((1, (0, 0)))
else:
q.append((0, (0, 0)))
dist = {}
while q:
cost, u = q.popleft()
if u in dist: continue
dist[u] = cost
x, y = u
if x == m - 1 and y == n - 1:
return cost
for dx, dy in Directions.dirs:
nx, ny = x + dx, y + dy
if nx < 0 or nx >= m or ny < 0 or ny >= n:
continue
v = (nx, ny)
if v in dist:
continue
if grid[nx][ny] == 1:
q.append((cost + 1, v))
else:
q.appendleft((cost, v))
return -1