<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 collections import deque

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        # run BFS while keeping track of how many obstacles have been removed for a path?

        # add (i, j) to visited when it is first visited by any path.
        visited = set() 

        m, n = len(grid), len(grid[0])

        # lets say we can remove exactly 1 obstacle. 
        # - let's start with standard BFS. if a node (i, j) is visited, we know the path
        #   to getting there from (0, 0) is the shortest path.
        # - suppose we encounter an obstable. we remove it - do we add this node to visited?
        # - let's add it as (i, j, 1) where 1 is the number of obstacles thus far removed
        #   - then as we proceed, we should check visited. don't visit any nodes with num nodes removed less than current nodes?
        queue = deque()

        if grid[0][0] <= k:
            queue.append((0, 0, grid[0][0], 0))
        
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        while queue:
            i, j, obstacles_seen, steps = queue.popleft()

            if i == m-1 and j == n-1:
                return steps

            # check all four corners. we can proceed if we haven't visited any nodes that have an equal 
            # or higher number of obstacles_seen
            for _i, _j in directions:
                x = i + _i
                y = j + _j
                
                # check bounds
                if x >= 0 and x <= m-1 and y >= 0 and y <= n-1:
                    # check that grid hasn't been visited by any paths with lower number of obstaces
                    skip_cell = False
                    for _obstacles in range(obstacles_seen):
                        if (x, y, _obstacles) in visited:
                            skip_cell = True
                        
                    if skip_cell is False:
                        if grid[x][y] == 0:
                            if (x, y, obstacles_seen) not in visited:
                                visited.add((x, y, obstacles_seen))
                                queue.append((x, y, obstacles_seen, steps+1))
                        else: 
                            # there is an obstacle - either increase obstacles_seen, or skip
                            if obstacles_seen < k:
                                if (x, y, obstacles_seen+1) not in visited:
                                    visited.add((x, y, obstacles_seen+1))
                                    queue.append((x, y, obstacles_seen+1, steps+1))

        return -1






18210