<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 Block:
    def __init__(self, obst, x, y, dir):
        self.obst = obst
        self.x = x
        self.y = y
        self.dir = dir
class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        from collections import deque

        n, m = len(grid), len(grid[0])
        p, q = 0, 0
        dq = deque()
        dq.append(Block(0, p, q, '_'))
        
        path = [['_' for _ in range(m)] for _ in range(n)]  # Initialize the path grid
        ans = ""
        
        while dq:
            front = dq.popleft()
            obstacle, x, y, dir = front.obst, front.x, front.y, front.dir
            
            if path[x][y] != '_':
                continue
            
            path[x][y] = dir
            
            if x == n - 1 and y == m-1:
                while not (x == p and y == q):
                    ans += path[x][y]
                    if path[x][y] == 'L':
                        y += 1
                    elif path[x][y] == 'R':
                        y -= 1
                    elif path[x][y] == 'D':
                        x -= 1
                    elif path[x][y] == 'U':
                        x += 1
                return obstacle
            
            if y > 0:
                if grid[x][y - 1] == 1:
                    dq.append(Block(obstacle + 1, x, y - 1, 'L'))
                else:
                    dq.appendleft(Block(obstacle, x, y - 1, 'L'))
            
            if y < m - 1:
                if grid[x][y + 1] == 1:
                    dq.append(Block(obstacle + 1, x, y + 1, 'R'))
                else:
                    dq.appendleft(Block(obstacle, x, y + 1, 'R'))
            
            if x > 0:
                if grid[x-1][y] == 1:
                    dq.append(Block(obstacle + 1, x-1, y, 'U'))
                else:
                    dq.appendleft(Block(obstacle, x-1, y, 'U'))
            if x < n - 1:
                if grid[x + 1][y] == 1:
                    dq.append(Block(obstacle + 1, x + 1, y, 'D'))
                else:
                    dq.appendleft(Block(obstacle, x + 1, y, 'D'))
    
    

49940