# Shortest Grid Path with Obstacle Eliminations Implement `shortest_path_with_eliminations(grid: list[list[int]], k: int) -> int`. The rectangular grid contains `0` for an open cell and `1` for an obstacle. Begin at the top-left cell and reach the bottom-right cell using four-direction moves. Entering an obstacle cell consumes one elimination. Return the minimum number of moves while consuming at most `k` eliminations. ### Input Domain - `1 <= rows, columns <= 40`. - Every cell is `0` or `1`; the start and destination cells are `0`. - `0 <= k <= rows * columns`. ### Output Rules - Return the minimum move count. - Return `0` for a one-cell grid. - Return `-1` when no path is possible within the elimination budget. - Only the distance is returned, so ties among shortest paths do not affect output. ### Constraints - A search state must distinguish positions reached with materially different remaining elimination budgets. - Target worst-case time and space are `O(rows * columns * (k + 1))`. ### Examples #### Example 1 Input: `grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1` Output: `6` #### Example 2 Input: `grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1` Output: `-1` ```hint Enrich the visited state Reaching one coordinate with more remaining eliminations can dominate reaching it at the same or a greater distance with fewer remaining eliminations. ```