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























class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = map(len, (grid, grid[0]))
        
        # dist: stores distance from the source (0,0) to every other cells
        dist = [[inf] * n for _ in range(m)]
        dist[0][0] = grid[0][0]

        # stores nodes to be examined
        pq = [(dist[0][0], 0, 0)]
        while pq:
            min_dist, r, c = heappop(pq)
            # min_dist: known min distance from source to (r, c)

            if (r, c) == (m - 1, n - 1):
                return min_dist
            
            for i, j in (r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1):
                if m > i >= 0 <= j < n and grid[i][j] + min_dist < dist[i][j]:
                    # (i, j)'s known min dist from (0,0) is dist[i][j]. 
                    # if dist[i][j] can be reduced by including (r, c) in the path, update dist[i][j].
                    #   (0,0) --> (r,c) --> (i,j)
                    dist[i][j] = grid[i][j] + min_dist
                    heappush(pq, (dist[i][j], i, j))
                    # if the current path (0,0) --> (r,c) --> (i,j) is shorter than the previously known path (0,0) --> (i, j), 
                    # (i, j)'s neighbors needs to be examined further based on the new shorter distance.
                    # So add (i, j) to pq. 
        return dist[-1][-1]



























class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        dist = [[float('inf')] * n for _ in range(m)]
        dist[0][0] = grid[0][0]
        pq = [(dist[0][0], 0, 0)]

        while pq:
            min_dist, y, x = heapq.heappop(pq)

            if y == m-1 and x == n-1:
                return min_dist

            for dydx in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                yy, xx = y + dydx[0], x + dydx[1]
                if not (0<=yy<m and 0<=xx<n):
                    continue
                dist_curr = min_dist + grid[yy][xx]
                if dist_curr < dist[yy][xx]:
                    dist[yy][xx] = dist_curr
                    heapq.heappush(pq, (dist_curr, yy, xx))
        return dist[-1][-1]



























class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        dist = [[float('inf')] * n for _ in range(m)]
        dist[0][0] = grid[0][0]
        pq = [(dist[0][0], 0, 0)]
        while pq:
            d, y, x = heapq.heappop(pq)
            if y == m-1 and x == n-1:
                return d

            for dydx in ((0,1), (0,-1), (1,0), (-1,0)):
                yy, xx = y + dydx[0], x + dydx[1]
                if not (0<=yy<m and 0<=xx<n):
                    continue
                if dist[yy][xx] > d + grid[yy][xx]:
                    dist[yy][xx] = grid[yy][xx] + d
                    heapq.heappush(pq, (dist[yy][xx], yy, xx))
        return dist[-1][-1]










class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dist = [[float('inf')] * n for _ in range(m)]
        dist[0][0] = grid[0][0]
        pq = [(dist[0][0], 0, 0)]

        while pq:
            min_dist, y, x = heapq.heappop(pq)
            if y == m-1 and x == n-1:
                return min_dist
            
            for dydx in ((0,1), (0,-1), (1,0), (-1,0)):
                yy, xx = y + dydx[0], x + dydx[1]
                if not (0<=yy<m and 0<=xx<n):
                    continue
                if dist[yy][xx] > min_dist + grid[yy][xx]:
                    dist[yy][xx] = min_dist + grid[yy][xx]
                    heapq.heappush(pq, (dist[yy][xx], yy, xx))
        return dist[-1][-1]




























class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[float('inf')] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        pq = [(dp[0][0], 0, 0)]
        while pq:
            dist, x, y = heapq.heappop(pq)
            if x == n-1 and y == m-1:
                return dist

            for dydx in ((0,1), (0,-1), (1,0), (-1,0)):
                yy, xx = y + dydx[0], x + dydx[1]
                if not (0<=yy<m and 0<=xx<n):
                    continue
                if dp[y][x] + grid[yy][xx] < dp[yy][xx]:
                    dp[yy][xx] = dp[y][x] + grid[yy][xx]
                    heapq.heappush(pq, (dp[yy][xx], xx, yy))
        return dp[-1][-1]





























class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[float('inf')] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        pq = [[dp[0][0], 0, 0]]
        while pq:
            dist, y, x = heapq.heappop(pq)
            if y == m-1 and x == n-1:
                return dist
            
            for dydx in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                yy, xx = y + dydx[0], x + dydx[1]
                if not (0<=yy<m and 0<=xx<n):
                    continue
                if dist + grid[yy][xx] < dp[yy][xx]:
                    dp[yy][xx] = dist + grid[yy][xx]
                    heapq.heappush(pq, [dp[yy][xx], yy, xx])
        return dp[-1][-1]


class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[float('inf')] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        queue = deque([[dp[0][0], 0, 0]])
        while queue:
            dist, y, x = queue.popleft()
            if y == m-1 and x == n-1:
                return dist

            for dydx in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                yy, xx = y + dydx[0], x + dydx[1]
                if not (0<=yy<m and 0<=xx<n):
                    continue
                if dp[yy][xx] == float('inf'):
                    dp[yy][xx] = dist + grid[yy][xx]
                    if grid[yy][xx] == 1:
                        queue.append([dp[yy][xx], yy, xx])
                    else:
                        queue.appendleft([dp[yy][xx], yy, xx])
                    
        return dp[-1][-1]



class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        # Initialize distances
        distances = [[float('inf')] * n for _ in range(m)]
        distances[0][0] = grid[0][0]

        # Relaxation process, we will perform (m * n - 1) iterations
        for _ in range(m * n - 1):
            for y in range(m):
                for x in range(n):
                    for dydx in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                        yy, xx = y + dydx[0], x + dydx[1]
                        if 0 <= yy < m and 0 <= xx < n:
                            if distances[y][x] + grid[yy][xx] < distances[yy][xx]:
                                distances[yy][xx] = distances[y][x] + grid[yy][xx]

        return distances[-1][-1]









class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        def heuristic(y, x):
            # Manhattan distance heuristic
            return (m - 1 - y) + (n - 1 - x)
        
        m, n = len(grid), len(grid[0])
        goal = (m - 1, n - 1)
        
        # Priority queue with elements (estimated_total_cost, current_cost, y, x)
        pq = [(heuristic(0, 0), 0, 0, 0)]
        distances = [[float('inf')] * n for _ in range(m)]
        distances[0][0] = 0
        
        while pq:
            estimated_total_cost, current_cost, y, x = heappop(pq)
            
            if (y, x) == goal:
                return current_cost
            
            for dydx in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                yy, xx = y + dydx[0], x + dydx[1]
                if 0 <= yy < m and 0 <= xx < n:
                    new_cost = current_cost + grid[yy][xx]
                    if new_cost < distances[yy][xx]:
                        distances[yy][xx] = new_cost
                        estimated_cost = new_cost + heuristic(yy, xx)
                        heappush(pq, (estimated_cost, new_cost, yy, xx))
        
        return distances[-1][-1]






























class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[float('inf')] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        pq = [[dp[0][0], 0, 0]]
        while pq:
            dist, y, x = heapq.heappop(pq)
            if y == m-1 and x == n-1:
                return dist
            
            for dydx in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                yy, xx = y + dydx[0], x + dydx[1]
                if not (0<=yy<m and 0<=xx<n):
                    continue
                if dist + grid[yy][xx] < dp[yy][xx]:
                    dp[yy][xx] = dist + grid[yy][xx]
                    heapq.heappush(pq, [dp[yy][xx], yy, xx])
        return dp[-1][-1]






class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[float('inf')] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        
        for _ in range(m*n):
            for y in range(m):
                for x in range(n):
                    for dydx in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                        yy, xx = dydx[0] + y, dydx[1] + x
                        if not (0<=yy<m and 0<=xx<n):
                            continue
                        if dp[y][x] + grid[yy][xx] < dp[yy][xx]:
                            dp[yy][xx] = dp[y][x] + grid[yy][xx]
        return dp[-1][-1]






























class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[float('inf')] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        pq = [(dp[0][0], 0, 0)]
        while pq:
            dist, y, x = heapq.heappop(pq)
            if y == m-1 and x == n-1:
                return dist
            
            for dydx in ((0,1), (0,-1), (1,0), (-1,0)):
                yy, xx = y + dydx[0], x + dydx[1]
                if not (0<=yy<m and 0<=xx<n):
                    continue
                if dist + grid[yy][xx] < dp[yy][xx]:
                    dp[yy][xx] = dist + grid[yy][xx]
                    heapq.heappush(pq, (dp[yy][xx], yy, xx))
        return dp[-1][-1]


class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[float('inf')] * n for _ in range(m)]
        dp[0][0] = grid[0][0]

        for _ in range(m*n):
            for y in range(m):
                for x in range(n):
                    for dydx in ((0,1), (0,-1), (1,0), (-1,0)):
                        yy, xx = y + dydx[0], x + dydx[1]
                        if not (0<=yy<m and 0<=xx<n):
                            continue
                        if dp[y][x] + grid[yy][xx] < dp[yy][xx]:
                            dp[yy][xx] = dp[y][x] + grid[yy][xx]
        return dp[-1][-1]






























class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        
        m, n = len(grid), len(grid[0])
        dp = [[float('inf')] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        pq = [(dp[0][0], 0, 0)]
        while pq:
            dist, y, x = heapq.heappop(pq)
            if y == m-1 and x == n-1:
                return dist
            
            for dydx in ((0,1), (0,-1), (1,0), (-1,0)):
                yy, xx = y + dydx[0], x + dydx[1]
                if not (0<=yy<m and 0<=xx<n):
                    continue
                if dist + grid[yy][xx] < dp[yy][xx]:
                    dp[yy][xx] = dist + grid[yy][xx]
                    heapq.heappush(pq, (dp[yy][xx], yy, xx))
        return dp[-1][-1]


class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        
        m, n = len(grid), len(grid[0])
        dp = [[float('inf')] * n for _ in range(m)]
        dp[0][0] = grid[0][0]

        for _ in range(m*n):
            for y in range(m):
                for x in range(n):
                    for dydx in ((0,1), (0,-1), (1,0), (-1,0)):
                        yy, xx = y + dydx[0], x + dydx[1]
                        if not (0<=yy<m and 0<=xx<n):
                            continue
                        if dp[y][x] + grid[yy][xx] < dp[yy][xx]:
                            dp[yy][xx] = dp[y][x] + grid[yy][xx]
        return dp[-1][-1]




























class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[float('inf')] * n for _ in range(m)]
        dp[0][0] = grid[0][0]

        pq = [(dp[0][0], 0, 0)]
        while pq:
            dist, y, x = heapq.heappop(pq)
            if y == m-1 and x == n-1:
                return dist
            
            for dydx in ((0,1), (0,-1), (1,0), (-1,0)):
                yy, xx = y + dydx[0], x + dydx[1]
                if not (0<=yy<m and 0<=xx<n):
                    continue
                if dist + grid[yy][xx] < dp[yy][xx]:
                    dp[yy][xx] = dist + grid[yy][xx]
                    heapq.heappush(pq, (dp[yy][xx], yy, xx))
        return dp[-1][-1]


class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[float('inf')] * n for _ in range(m)]
        dp[0][0] = grid[0][0]

        for _ in range(m*n):
            for y in range(m):
                for x in range(n):
                    for dydx in ((0,1), (0,-1), (1,0), (-1,0)):
                        yy, xx = y + dydx[0], x + dydx[1]
                        if not (0<=yy<m and 0<=xx<n):
                            continue
                        if dp[y][x] + grid[yy][xx] < dp[yy][xx]:
                            dp[yy][xx] = dp[y][x] + grid[yy][xx]
        return dp[-1][-1]































class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[float('inf')] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        pq = [(dp[0][0], 0, 0)]
        while pq:
            dist, y, x = heapq.heappop(pq)
            if y==m-1 and x == n-1:
                return dist

            for dydx in ((0,1), (0,-1), (1,0), (-1,0)):
                yy, xx = y + dydx[0], x + dydx[1]
                if not (0<=yy<m and 0<=xx<n):
                    continue
                if dist + grid[yy][xx] < dp[yy][xx]:
                    dp[yy][xx] = dist + grid[yy][xx]
                    heapq.heappush(pq, (dp[yy][xx], yy, xx))
        return dp[-1][-1]


class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[float('inf')] * n for _ in range(m)]
        dp[0][0] = grid[0][0]

        for _ in range(m*n):
            for y in range(m):
                for x in range(n):
                    for dydx in ((0,1), (0,-1), (1,0), (-1,0)):
                        yy, xx = y + dydx[0], x + dydx[1]
                        if not (0<=yy<m and 0<=xx<n):
                            continue
                        if dp[yy][xx] > dp[y][x] + grid[yy][xx]:
                            dp[yy][xx] = dp[y][x] + grid[yy][xx]
        return dp[-1][-1]


























class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[float('inf')] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        pq = [(0, 0, 0)] # dist, y, x
        while pq:
            dist, y, x = heapq.heappop(pq)
            if y == m-1 and x == n-1:
                return dist
            for dydx in ((0,1), (0,-1), (1,0), (-1,0)):
                yy, xx = y + dydx[0], x + dydx[1]
                if not (0<=yy<m and 0<=xx<n):
                    continue
                if dist + grid[yy][xx] < dp[yy][xx]:
                    dp[yy][xx] = grid[yy][xx] + dist
                    heapq.heappush(pq, (dp[yy][xx], yy, xx))
        return dp[-1][-1]























class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[float('inf')] * n for _ in range(m)]
        dp[0][0] = grid[0][0]

        pq = [(dp[0][0], 0, 0)] # dist, y, x
        while pq:
            dist, y, x = heapq.heappop(pq)
            if y == m-1 and x == n-1:
                return dist

            for dydx in ((0,1), (0,-1), (1,0), (-1,0)):
                yy, xx = dydx[0] + y, dydx[1] + x
                if not (0<=yy<m and 0<=xx<n):
                    continue
                if dist + grid[yy][xx] < dp[yy][xx]:
                    heapq.heappush(pq, (dist+grid[yy][xx], yy, xx))
                    dp[yy][xx] = dist + grid[yy][xx]
        return dp[-1][-1] if dp[-1][-1] != float('inf') else -1


class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[float('inf')] * n for _ in range(m)]
        dp[0][0] = grid[0][0]

        for _ in range(m*n):
            for y in range(m):
                for x in range(n):
                    for dydx in ((0,1), (0,-1), (1,0), (-1,0)):
                        yy, xx = dydx[0] + y, dydx[1] + x
                        if not (0<=yy<m and 0<=xx<n):
                            continue
                        if dp[y][x] + grid[yy][xx] < dp[yy][xx]:
                            dp[yy][xx] = dp[y][x] + grid[yy][xx]
        return dp[-1][-1] if dp[-1][-1] != float('inf') else -1




























class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[float('inf')] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        pq = [(dp[0][0], 0, 0)]
        while pq:
            cost, y, x = heapq.heappop(pq)
            if y == m-1 and x == n-1:
                return cost
            
            for dydx in ((0, 1), (0,-1), (1,0), (-1,0)):
                yy, xx = y + dydx[0], x + dydx[1]
                if not (0<=yy<m and 0<=xx<n):
                    continue
                if cost + grid[yy][xx] < dp[yy][xx]:
                    dp[yy][xx] = cost + grid[yy][xx]
                    heapq.heappush(pq, (dp[yy][xx], yy, xx))
        return dp[-1][-1] if dp[-1][-1] != float('inf') else -1


class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[float('inf')] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        for _ in range(m*n):
            for y in range(m):
                for x in range(n):
                    for dydx in ((0,1), (0,-1), (1,0), (-1,0)):
                        yy, xx = y + dydx[0], x + dydx[1]
                        if not (0<=yy<m and 0<=xx<n):
                            continue
                        if dp[yy][xx] > dp[y][x] + grid[yy][xx]:
                            dp[yy][xx] = dp[y][x] + grid[yy][xx]
        return dp[-1][-1]


























class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        
        m, n = len(grid), len(grid[0])
        costs = [[float('inf')] * n for _ in range(m)]
        costs[0][0] = grid[0][0]
        pq = [(costs[0][0], 0, 0)]
        while pq:
            cost, y, x = heapq.heappop(pq)
            if y == m-1 and x == n-1:
                return cost

            for dydx in ((0,1), (0,-1), (1,0), (-1,0)):
                yy, xx = dydx[0] + y, dydx[1] + x
                if not (0<=yy<m and 0<=xx<n):
                    continue
                if cost + grid[yy][xx] < costs[yy][xx]:
                    costs[yy][xx] = cost + grid[yy][xx]
                    heapq.heappush(pq, (costs[yy][xx], yy, xx))
        return costs[m-1][n-1]


class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        costs = [[float('inf')] * n for _ in range(m)]
        costs[0][0] = grid[0][0]
        
        for _ in range(m*n):
            for y in range(m):
                for x in range(n):
                    for dydx in ((0,1), (0,-1), (1,0), (-1,0)):
                        yy, xx = dydx[0] + y, dydx[1] + x
                        if not (0<=yy<m and 0<=xx<n):
                            continue
                        if costs[y][x] + grid[yy][xx] < costs[yy][xx]:
                            costs[yy][xx] = costs[y][x] + grid[yy][xx]
        return costs[m-1][n-1]























class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        # dijkstra
        m, n = len(grid), len(grid[0])
        costs = [[float('inf')] * n for _ in range(m)]
        costs[0][0] = grid[0][0]
        pq = [(costs[0][0], 0, 0)]
        while pq:
            cost, y, x = heapq.heappop(pq)
            if y == m-1 and x == n-1:
                return cost
            for dydx in ((0,1), (0,-1), (1,0), (-1,0)):
                yy, xx = y + dydx[0], x + dydx[1]
                if not (0<=yy<m and 0<=xx<n):
                    continue
                if cost + grid[yy][xx] < costs[yy][xx]:
                    costs[yy][xx] = cost + grid[yy][xx]
                    heapq.heappush(pq, ((costs[yy][xx], yy, xx)))
        return costs[m-1][n-1]


class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        # Bellman-Ford
        m, n = len(grid), len(grid[0])
        costs = [[float('inf')] * n for _ in range(m)]
        costs[0][0] = grid[0][0]

        for _ in range(m * n):
            for y in range(m):
                for x in range(n):
                    for dydx in ((0,1), (0,-1), (1,0), (-1,0)):
                        yy, xx = y + dydx[0], x + dydx[1]
                        if not (0<=yy<m and 0<=xx<n):
                            continue
                        if costs[y][x] + grid[yy][xx] < costs[yy][xx]:
                            costs[yy][xx] = costs[y][x] + grid[yy][xx]
        return costs[m-1][n-1]

























class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        # dijkstra
        m, n = len(grid), len(grid[0])
        costs = collections.defaultdict(lambda: float('inf'))
        costs[(0,0)] = grid[0][0]
        pq = [(grid[0][0], 0, 0)] # cost, y, x
        while pq:
            cost, y, x = heapq.heappop(pq)
            if y == m-1 and x == n-1:
                return cost
            for dydx in ((0,1), (0,-1), (1,0), (-1,0)):
                yy, xx = y + dydx[0], x + dydx[0]
                if not (0<=yy<m and 0<=xx<n):
                    continue
                if cost + grid[yy][xx] < costs[(yy, xx)]:
                    costs[(yy, xx)] = cost + grid[yy][xx]
                    heapq.heappush(pq, (cost+grid[yy][xx], yy, xx))
        return costs[(m-1, n-1)]


class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        # dijkstra
        m, n = len(grid), len(grid[0])
        costs = [[float('inf')] * n for _ in range(m)]
        costs[0][0] = grid[0][0]
        pq = [(grid[0][0], 0, 0)] # cost, y, x
        while pq:
            cost, y, x = heapq.heappop(pq)
            if y == m-1 and x == n-1:
                return cost
            for dydx in ((0,1), (0,-1), (1,0), (-1,0)):
                yy, xx = y + dydx[0], x + dydx[1]
                if not (0<=yy<m and 0<=xx<n):
                    continue
                if cost + grid[yy][xx] < costs[yy][xx]:
                    costs[yy][xx] = cost + grid[yy][xx]
                    heapq.heappush(pq, (cost+grid[yy][xx], yy, xx))
        return costs[-1][-1]

2464