<p>You are given an <code>m x n</code> integer matrix <code>grid</code> where each cell is either <code>0</code> (empty) or <code>1</code> (obstacle). You can move up, down, left, or right from and to an empty cell in <strong>one step</strong>.</p>

<p>Return <em>the minimum number of <strong>steps</strong> to walk from the upper left corner </em><code>(0, 0)</code><em> to the lower right corner </em><code>(m - 1, n - 1)</code><em> given that you can eliminate <strong>at most</strong> </em><code>k</code><em> obstacles</em>. If it is not possible to find such walk return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/09/30/short1-grid.jpg" style="width: 244px; height: 405px;" />
<pre>
<strong>Input:</strong> grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
<strong>Output:</strong> 6
<strong>Explanation:</strong> 
The shortest path without eliminating any obstacle is 10.
The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -&gt; (0,1) -&gt; (0,2) -&gt; (1,2) -&gt; (2,2) -&gt; <strong>(3,2)</strong> -&gt; (4,2).
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/09/30/short2-grid.jpg" style="width: 244px; height: 245px;" />
<pre>
<strong>Input:</strong> grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1
<strong>Output:</strong> -1
<strong>Explanation:</strong> We need to eliminate at least two obstacles to find such a walk.
</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;= 40</code></li>
	<li><code>1 &lt;= k &lt;= m * n</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 shortestPath(self, grid: List[List[int]], k: int) -> int:
        pass




























class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        queue = deque([(0,0, k)])
        seen = set()
        dist = 0
        while queue:
            queue_next = deque()
            while queue:
                y, x, k_rem = 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 grid[yy][xx] == 0:
                        if (yy, xx, k_rem) not in seen:
                            seen.add((yy, xx, k_rem))
                            queue_next.append((yy, xx, k_rem))
                    else:
                        if k_rem > 0:
                            if (yy, xx, k_rem-1) not in seen:
                                seen.add((yy, xx, k_rem-1))
                                queue_next.append((yy, xx, k_rem-1))
            queue = queue_next
            dist += 1
        return -1

import heapq

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

        # Heuristic function: Manhattan distance to the goal
        def heuristic(y, x):
            return (m - 1 - y) + (n - 1 - x)

        # Priority queue to store (estimated_total_cost, current_distance, y, x, remaining_k)
        pq = [(heuristic(0, 0), 0, 0, 0, k)]
        seen = {(0, 0, k)}

        while pq:
            est_total_cost, dist, y, x, k_rem = 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 grid[yy][xx] == 0:
                    if (yy, xx, k_rem) not in seen:
                        seen.add((yy, xx, k_rem))
                        heapq.heappush(pq, (dist + 1 + heuristic(yy, xx), dist + 1, yy, xx, k_rem))
                else:
                    if k_rem > 0:
                        if (yy, xx, k_rem - 1) not in seen:
                            seen.add((yy, xx, k_rem - 1))
                            heapq.heappush(pq, (dist + 1 + heuristic(yy, xx), dist + 1, yy, xx, k_rem - 1))
        
        return -1


class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:

        rows, cols = len(grid), len(grid[0])
        target = (rows - 1, cols - 1)

        def manhattan_distance(row, col):
            # distance from current location to the target.
            return target[0] - row + target[1] - col

        # (row, col, remaining_elimination)
        state = (0, 0, k)

        # (estimation, steps, state)
        # h(n) = manhattan distance,  g(n) = 0
        queue = [(manhattan_distance(0, 0), 0, state)]
        seen = set([state])

        while queue:
            estimation, steps, (row, col, remain_eliminations) = heapq.heappop(queue)
            # estimation: estimated total costs (0,0) -a-> (row, col) -b-> (target location)
            #   It consists of prior path cost (a) and future path distance (b). 

            remain_min_distance = estimation - steps
            # Only includes future path distance

            # we can reach the target in the shortest path (manhattan distance),
            #   even if the remaining steps are all obstacles
            if remain_min_distance <= remain_eliminations:
                return estimation

            # explore the four directions in the next step
            for new_row, new_col in [(row, col + 1), (row + 1, col), (row, col - 1), (row - 1, col)]:
                # if (new_row, new_col) is within the grid boundaries
                if (0 <= new_row < rows) and (0 <= new_col < cols):
                    new_eliminations = remain_eliminations - grid[new_row][new_col]
                    new_state = (new_row, new_col, new_eliminations)

                    # if the next direction is worth exploring
                    if new_eliminations >= 0 and new_state not in seen:
                        seen.add(new_state)
                        new_estimation = manhattan_distance(new_row, new_col) + steps + 1
                        heapq.heappush(queue, (new_estimation, steps + 1, new_state))

        # did not reach the target
        return -1



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

        def manhattan_distance(y, x):
            # distance from current location to the target.
            return m-1-y + n-1-x

        # (row, col, remaining quota to eliminate obstacles)
        state = (0, 0, k)
        # (cost_future, cost_past, state)
        pq = [(manhattan_distance(0,0), 0, state)]
        seen = set([state])

        while pq:
            #print(heapq.heappop(pq))
            cost_total, cost_past, (y, x, k_rem) = heapq.heappop(pq)
            cost_future = cost_total - cost_past
            if cost_future <= k_rem:
                return cost_total

            # we reach the target here
            if y == m-1 and x == n-1:
                return cost_past

            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
                
                new_k_rem = k_rem - grid[yy][xx]  # FIXED: Calculate new_k_rem separately
                if new_k_rem < 0:
                    continue
                new_state = (yy, xx, new_k_rem)  # FIXED: Create new_state with new_k_rem
                if new_state not in seen:
                    seen.add(new_state)
                    heapq.heappush(pq, (cost_past + 1 + manhattan_distance(yy, xx), cost_past + 1, new_state))  # FIXED: Use new_k_rem in new_state and push to pq
                
        # did not reach the target
        return -1



class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        queue = deque([(0,0, k)])
        seen = set()
        dist = 0
        while queue:
            queue_next = deque()
            while queue:
                y, x, k_rem = 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

                    k_rem_new = k_rem - grid[yy][xx]
                    if k_rem_new < 0:
                        continue
                    if (yy, xx, k_rem_new) not in seen:
                        seen.add((yy, xx, k_rem_new))
                        queue_next.append((yy, xx, k_rem_new))

            queue = queue_next
            dist += 1
        return -1


























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

        def dist(y, x):
            # calculate distance from the current (y, x) to target
            return m-1-y+n-1-x
        
        seen = set([(0, 0, k)])
        pq = [(dist(0,0), 0, 0, 0, k)] # dist_total, dist_past, y, x, k_rem
        while pq:
            dist_total, dist_past, y, x, k_rem = heapq.heappop(pq)
            dist_future = dist_total - dist_past
            if y == m-1 and x == n-1:
                return dist_past
            if dist_future < k_rem:
                return cost_total
            
            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
                k_rem_new = k_rem - grid[yy][xx]
                if k_rem_new < 0:
                    continue
                dist_total_new = dist_past + 1 + dist(yy, xx)
                if (yy, xx, k_rem_new) not in seen:
                    seen.add((yy, xx, k_rem_new))
                    heapq.heappush(pq, (dist_total_new, dist_past+1, yy, xx, k_rem_new))
        return -1

























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

        def h_dist(y, x):
            # calculate distance from (y,x) to the target
            return m-1-y + n-1-x

        seen = set([(0, 0, k)])
        pq = [(h_dist(0,0), 0, 0, 0, k)] # dist_total, dist_past, y, x, krem
        while pq:
            dist_total, dist_past, y, x, krem = heapq.heappop(pq)
            if y == m-1 and x == n-1:
                return dist_past
            
            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
                
                new_krem = krem - grid[yy][xx]
                if new_krem >= 0:
                    new_dist_past = dist_past + 1
                    new_dist_future = h_dist(yy, xx)
                    new_dist_total = new_dist_past + new_dist_future
                    if (yy, xx, new_krem) not in seen:
                        seen.add((yy, xx, new_krem))
                        heapq.heappush(pq, (new_dist_total, new_dist_past, yy, xx, new_krem))
        return -1




























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

        def h_dist(y, x):
            return m-1-y+n-1-x

        pq = [(h_dist(0, 0), 0, 0, 0, 0)] # cost_all, cost_past, y, x, krem
        seen = set([(0, 0, 0)])
        while pq:
            cost_all, cost_past, y, x, krem = heapq.heappop(pq)
            if y == m-1 and x == n-1:
                return cost_past

            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
                krem_new = krem + grid[yy][xx]
                if krem_new > k:
                    continue
                cost_future_new = h_dist(yy, xx)
                cost_past_new = cost_past + 1
                cost_all_new = cost_future_new + cost_past_new
                if (yy, xx, krem_new) not in seen:
                    heapq.heappush(pq, (cost_all_new, cost_past_new, yy, xx, krem_new))
                    seen.add((yy, xx, krem_new))
        return -1


class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[float('inf')] * n for _ in range(m)]
        dp[0][0] = 0
        pq = [(0, 0, 0, grid[0][0])]
        while pq:
            cost, y, x, krem = heapq.heappop(pq)
            if y == m-1 and x == n-1:
                print(dp)
                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
                krem_new = krem + grid[yy][xx]
                if krem_new > k:
                    continue
                if dp[yy][xx] > cost + grid[yy][xx]:
                    dp[yy][xx] = cost + grid[yy][xx]
                    heapq.heappush(pq, (dp[yy][xx], yy, xx, krem_new))
        return -1


class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[[float('inf')] * (k+1) for _ in range(n)] for _ in range(m)]
        dp[0][0][0] = 0
        pq = [(0, 0, 0, grid[0][0])] # cost, y, x, krem
        while pq:
            cost, y, x, krem = 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
                krem_new = krem + grid[yy][xx]
                if krem_new > k:
                    continue
                if dp[yy][xx][krem_new] > cost + 1:
                    dp[yy][xx][krem_new] = cost + 1
                    heapq.heappush(pq, (dp[yy][xx][krem_new], yy, xx, krem_new))
        return -1




























class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        
        def distance(y, x):
            # distance from the current location to the target
            return m-1-y + n-1-x

        m, n = len(grid), len(grid[0])
        pq = []
        heapq.heappush(pq, (distance(0,0), 0, 0, 0, k))
        # dist_all, dist_past, y, x, krem
        seen = set([(0, 0, k)])
        while pq:
            dist_all, dist_past, y, x, krem = heapq.heappop(pq)
            if y == m-1 and x == n-1:
                return dist_all
            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
                krem_new = krem - grid[yy][xx]
                if krem_new >= 0:
                    dist_future_new = distance(yy, xx)
                    dist_past_new = dist_past + 1
                    dist_all_new = dist_future_new + dist_past_new
                    if (yy, xx, krem_new) not in seen:
                        heapq.heappush(pq, (dist_all_new, dist_past_new, yy, xx, krem_new))
                        seen.add((yy, xx, krem_new))
        return -1




























class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        def distance(y, x):
            # return dist from (y,x) to target
            return m-1-y + n-1-x
        
        seen = set((0,0,k))
        m, n = len(grid), len(grid[0])
        pq = [(distance(0,0), 0, 0, 0, k)] # dist_all, dist_past, y, x, krem
        while pq:
            dist_all, dist_past, y, x, krem = heapq.heappop(pq)
            if y == m-1 and x == n-1:
                return dist_all
            
            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
                krem_new = krem - grid[yy][xx]
                if krem_new >= 0:
                    dist_past_new = dist_past + 1
                    dist_future_new = distance(yy, xx)
                    dist_all_new = dist_past_new + dist_future_new
                    if (yy, xx, krem_new) not in seen:
                        seen.add((yy, xx, krem_new))
                        heapq.heappush(pq, (dist_all_new, dist_past_new, yy, xx, krem_new))
        return -1
























class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        # A* algorithm

        m, n = len(grid), len(grid[0])
        def dist(y, x):
            # return distance from (y, x) to end point
            return m-1-y + n-1-x
        
        pq = [(dist(0,0), 0, 0, 0, grid[0][0])] # dist_all, dist_past, y, x, k_rem
        seen = set([(0, 0, grid[0][0])])
        while pq:
            dist_all, dist_past, y, x, k_rem = heapq.heappop(pq)
            dist_future = dist_all - dist_past
            if y == m-1 and x == n-1:
                if k_rem <= k:
                    return dist_all
            
            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
                new_dist_future = dist(yy, xx)
                new_dist_past = dist_past + 1
                new_dist_all = new_dist_future + new_dist_past
                if (yy, xx, k_rem+grid[yy][xx]) not in seen:
                    seen.add((yy, xx, k_rem+grid[yy][xx]))
                    if k_rem + grid[yy][xx] <= k:
                        heapq.heappush(pq, (new_dist_all, new_dist_past, yy, xx, k_rem+grid[yy][xx]))
        return -1
21036