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

Return _the minimum number of **steps** to walk from the upper left corner_ `(0, 0)` _to the lower right corner_ `(m - 1, n - 1)` _given that you can eliminate **at most**_ `k` _obstacles_. If it is not possible to find such walk return `-1`.

**Example 1:**

**Input:** grid = \[\[0,0,0\],\[1,1,0\],\[0,0,0\],\[0,1,1\],\[0,0,0\]\], k = 1
**Output:** 6
**Explanation:** 
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) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> **(3,2)** -> (4,2).

**Example 2:**

**Input:** grid = \[\[0,1,1\],\[1,1,1\],\[1,0,0\]\], k = 1
**Output:** -1
**Explanation:** We need to eliminate at least two obstacles to find such a walk.

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `1 <= m, n <= 40`
*   `1 <= k <= m * n`
*   `grid[i][j]` is either `0` **or** `1`.
*   `grid[0][0] == grid[m - 1][n - 1] == 0`


from collections import deque


def shortestPath(grid, k):
    m, n = len(grid), len(grid[0])
    visited = [[[False for _ in range(k + 1)] for _ in range(n)] for _ in range(m)]
    q = deque([(0, 0, 0, k)])
    moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    steps = 0

    while q:
        for _ in range(len(q)):
            x, y, steps, k_remaining = q.popleft()
            if x == m - 1 and y == n - 1:
                return steps
            for dx, dy in moves:
                new_x, new_y, = x + dx, y + dy
                if 0 <= new_x < m and 0 <= new_y < n:
                    new_k_remaining = k_remaining - grid[new_x][new_y]
                    if new_k_remaining >= 0 and not visited[new_x][new_y][new_k_remaining]:
                        visited[new_x][new_y][new_k_remaining] = True
                        q.append((new_x, new_y, steps + 1, new_k_remaining))
        steps += 1

    return -1
