DELTAS = [(-1, 0), (0, -1), (1, 0), (0, 1)]

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

        if k >= W + H - 2:
            return W + H - 2

        dist = [[None] * H for _ in range(W)]
        dist[0][0] = 0

        obstacles = []
        for x in range(W):
            for y in range(H):
                if grid[x][y] == 1:
                    obstacles.append((x, y))

        def min_neighbour(x: int, y: int) -> Optional[int]:
            ans = None
            for dx, dy in DELTAS:
                nx, ny = x + dx, y + dy
                if not (0 <= nx < W and 0 <= ny < H):
                    continue
                if dist[nx][ny] is None:
                    continue
                if ans is None or dist[nx][ny] < ans:
                    ans = dist[nx][ny]
            return ans


        for ki in range(k + 1):
            q = []  # tuples of (dist, x, y)
            if ki == 0:
                q.append((0, 0, 0))
            else:
                for x, y in obstacles:
                    ndist = min_neighbour(x, y)
                    if ndist is None:
                        continue
                    if dist[x][y] is None or ndist + 1 < dist[x][y]:
                        q.append((ndist + 1, x, y))
                for cdist, x, y in q:
                    dist[x][y] = cdist
            heapify(q)

            while q:
                cdist, x, y = heappop(q)
                if dist[x][y] > cdist:
                    continue
                for dx, dy in DELTAS:
                    nx, ny = x + dx, y + dy
                    if not (0 <= nx < W and 0 <= ny < H):
                        continue
                    if grid[nx][ny] == 1:
                        continue
                    ndist = cdist + 1
                    if dist[nx][ny] is None or ndist < dist[nx][ny]:
                        dist[nx][ny] = ndist
                        heappush(q, (dist[nx][ny], nx, ny))

            # for row in dist:
            #     print(row)
            # print()

        return dist[-1][-1] if dist[-1][-1] is not None else -1