<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>

class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        
        row = len(grid)
        
        col = len(grid[0])
        
        directions = [ [1,0], [0,1], [-1,0], [0,-1] ]
        
        isValid = lambda x,y:x > -1 and x < row and y > -1 and y < col
        
        vis = set()
        
        def bfs():
            
            que = deque([ [0,0,0] ] )
            
            vis.add((0,0))
            
            while que:
                
                x,y,cost = que.popleft()
                
                if x==row-1 and y == col-1:
                    
                    return cost
                
                for x1,y1 in directions:
                
                    new_x, new_y = x + x1, y + y1
                    
                    
                    if isValid(new_x, new_y) and (new_x, new_y) not in vis:
                        
                        vis.add((new_x, new_y))
                        
                        if grid[new_x][new_y] == 0:
                            
                            que.appendleft( [new_x, new_y, cost] )
                            
                        else:
                            
                            que.append( [new_x, new_y, cost+1] )
                            
            
            return -1
        
        return bfs()
                
                
        
        flat = lambda x,y: x*col + y
        
        INF = 10**18
        
        dist = [INF]*(row * col)
        
        dist[0] = 0
        
        min_heap = list()
        
        vis = set()
        
        heappush(min_heap, [0,0])
        
        while min_heap:
            
            curr_weight, node = heappop(min_heap)
            
            if node in vis:
                
                continue
                
            vis.add(node)
            
            x,y = node // col, node % col
            
            for x1,y1 in directions:
                
                new_x, new_y = x + x1, y + y1
                
                curr_node = flat(new_x, new_y)
                
                if isValid(new_x, new_y) and dist[curr_node] > dist[node] + grid[new_x][new_y]:
                    
                    dist[curr_node] = dist[node] + grid[new_x][new_y]
    
                    heappush(min_heap,[dist[node] + grid[new_x][new_y], curr_node])
        
        
        print(dist)
        return dist[row*col-1]

2658