<p>You are given a <strong>0-indexed</strong> 2D integer array <code>grid</code> of size <code>m x n</code>. Each cell has one of two values:</p>

<ul>
	<li><code>0</code> represents an <strong>empty</strong> cell,</li>
	<li><code>1</code> represents an <strong>obstacle</strong> that may be removed.</li>
</ul>

<p>You can move up, down, left, or right from and to an empty cell.</p>

<p>Return <em>the <strong>minimum</strong> number of <strong>obstacles</strong> to <strong>remove</strong> so you can move from the upper left corner </em><code>(0, 0)</code><em> to the lower right corner </em><code>(m - 1, n - 1)</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/04/06/example1drawio-1.png" style="width: 605px; height: 246px;" />
<pre>
<strong>Input:</strong> grid = [[0,1,1],[1,1,0],[1,1,0]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> We can remove the obstacles at (0, 1) and (0, 2) to create a path from (0, 0) to (2, 2).
It can be shown that we need to remove at least 2 obstacles, so we return 2.
Note that there may be other ways to remove 2 obstacles to create a path.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/04/06/example1drawio.png" style="width: 405px; height: 246px;" />
<pre>
<strong>Input:</strong> grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
<strong>Output:</strong> 0
<strong>Explanation:</strong> We can move from (0, 0) to (2, 4) without removing any obstacles, so we return 0.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li>
	<li><code>2 &lt;= m * n &lt;= 10<sup>5</sup></code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> <strong>or</strong> <code>1</code>.</li>
	<li><code>grid[0][0] == grid[m - 1][n - 1] == 0</code></li>
</ul>

from collections import deque

class Solution:
    # SPFA
#     def minimumObstacles(self, grid: List[List[int]]) -> int:
#         m, n = len(grid), len(grid[0])
#         directions = [[0, 1], [1, 0], [-1, 0], [0, -1]]
        
#         min_obstacles = [[float("inf")] * n for _ in range(m)]
#         min_obstacles[0][0] = 0
        
#         queue = deque([(0, 0)])
#         enqueued = set([(0, 0)])
#         while len(queue) > 0:
#             x, y = queue.popleft()
#             enqueued.remove((x, y))
#             for dx, dy in directions:
#                 new_x, new_y = x + dx, y + dy
#                 if new_x < 0 or new_x >= m or new_y < 0 or new_y >= n:
#                     continue
                
#                 obstacles = min_obstacles[x][y] + (1 if grid[x][y] == 1 else 0)
#                 if obstacles >= min_obstacles[new_x][new_y]:
#                     continue
                
#                 min_obstacles[new_x][new_y] = obstacles
#                 if (new_x, new_y) in enqueued:
#                     continue
                
#                 queue.append((new_x, new_y))
#                 enqueued.add((new_x, new_y))
            
#         return min_obstacles[-1][-1]

    # DIJKSTRA
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        directions = [[0, 1], [1, 0], [-1, 0], [0, -1]]
        
        # min_obstacles = [[float("inf")] * n for _ in range(m)]
        # min_obstacles [0][0] = 0
        seen = set([(0, 0)])
        updated_nodes = [(0, 0, 0)]
        while len(updated_nodes) > 0:
            obstacles, x, y = heapq.heappop(updated_nodes)
            if (x, y) == (m-1, n-1):
                return obstacles

            for dx, dy in directions:
                new_x, new_y = x + dx, y + dy
                if new_x < 0 or new_x >= m or new_y < 0 or new_y >= n:
                    continue
                
                if (new_x, new_y) in seen:
                    continue
                
                new_obstacles = obstacles + grid[new_x][new_y]
                seen.add((new_x, new_y))

                heapq.heappush(updated_nodes, (new_obstacles, new_x, new_y))




#     def minimumObstacles(self, grid: List[List[int]]) -> int:
#         #find the min cost path from (0,0) to (m-1, n-1)
#         m = len(grid); n = len(grid[0])

#         heap = [[grid[0][0], 0, 0]]
#         visited = [[0]*n for _ in range(m)]
#         visited[0][0] = 1
#         while heap:
#             c_cost, c_i, c_j = heappop(heap)
#             if (c_i,c_j) == (m-1,n-1):
#                 return c_cost
#             for n_i,n_j in [[c_i-1,c_j], [c_i,c_j+1], [c_i+1,c_j], [c_i,c_j-1]]:
#                 if 0<=n_i<m and 0<=n_j<n and not visited[n_i][n_j]:
#                     visited[n_i][n_j] = 1
#                     heappush(heap, [c_cost + grid[n_i][n_j], n_i, n_j])

#         return -1
        
        
        
                
                
2755