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

from dataclasses import dataclass
from queue import Queue

@dataclass(frozen=True)
class Node:
    x: int
    y: int
    barriers: int

def get_adjacent(node: Node, grid, max_x, max_y) -> [Node]:      

    neighbors = []

    for x_delta, y_delta in [ (-1, 0), (1, 0), (0, 1), (0,-1)]:
        new_x = node.x + x_delta
        new_y = node.y + y_delta

        if new_x < 0 or new_x > max_x or new_y < 0 or new_y > max_y:
            # Node is outside the grid
            continue
        
        new_barriers = node.barriers + grid[new_x][new_y]
        neighbors.append(Node(new_x, new_y, new_barriers))
    
    return neighbors
    


class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        start_x = 0
        start_y = 0
        barriers = grid[0][0]

        end_x = len(grid) - 1
        end_y = len(grid[0]) - 1

        start_node = Node(start_x, start_y, 0)

        to_visit = Queue()
        to_visit.put((start_node, 0))

        visited = set()

        shortest_path_steps = -1

        while not to_visit.empty():
            node, steps = to_visit.get()

            if node in visited:
                continue
            
            visited.add(node)

            if shortest_path_steps > 0 and shortest_path_steps < steps:
                # This path is as good as or worse than the best path so far
                continue
            if node.barriers > k:
                # Out of bounds
                continue
            
            if node.x == end_x and node.y == end_y:
                if shortest_path_steps < 0 or steps < shortest_path_steps:
                    # We've found the new shortest path
                    shortest_path_steps = steps
                # No point searching from here
                continue
            
            next_nodes = get_adjacent(node, grid, end_x, end_y)
            for a_node in next_nodes:
                to_visit.put((a_node, steps + 1))


        return shortest_path_steps


        
27730