<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:
        # I can model this as a 0/1 Shortest path problem: i.e. SP in a weighted graph, but where weigths are only 0 or 1 (special easier case than the general weighted graph SP problem)
        # in this case the edge with weight 0 is one going from any vertex to an empty vertex (value: 0), and an edge with weight 1 is one going from any vertex to an obstacle vertex (value: 1)

        self.rows = len(grid)
        self.cols = len(grid[0])
        self.directions = [(1,0), (0,1), (-1,0), (0,-1)]
        self.grid = grid
        self.pred = [[()] * self.cols for i in range(self.rows)]  # (r,c) -> predecessor (r_pred, c_pred) tuple
        self.dist = [[float("+inf")] * self.cols for i in range(self.rows)]  # (r,c) -> distance (int) 
        self.bfs_01(0,0)
        return self.dist[self.rows - 1][self.cols - 1]
    


    def bfs_01(self,r,c):
        queue = deque()
        queue.append((r,c))
        self.dist[r][c] = 0
        while queue:
            curr_r, curr_c = queue.popleft()
            # remember to appendleft then
            for dr, dc in self.directions:
                next_r, next_c = curr_r + dr, curr_c + dc
                if next_r < 0 or next_r >= self.rows or next_c < 0 or next_c >= self.cols: continue # Out of Bounds!
                # compute new distance
                new_distance = self.dist[curr_r][curr_c] + self.grid[next_r][next_c]
                if new_distance < self.dist[next_r][next_c]:
                    self.dist[next_r][next_c] = new_distance
                    self.pred[next_r][next_c] = (curr_r, curr_c)
                    if self.grid[next_r][next_c] == 0:
                        queue.appendleft((next_r, next_c))
                    elif self.grid[next_r][next_c] == 1:
                        queue.append((next_r, next_c))
                    
54260