Given a m * n grid, where each cell is either 0 (empty) or 1 (obstacle). In one step, you can move up, down, left or right from and to an empty cell.
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:

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

Difficulty: MEDIUM
Tags: Matrices

Data structures

Graph traversal
Skill types: Data structures

Starter code:
class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        

Solutions:
class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(rows, cols) = (len(grid), len(grid[0]))
		(steps, min_steps) = (0, rows + cols - 2)
		if k >= min_steps - 1:
			return min_steps
		visited = [[-1] * cols for _ in range(rows)]
		visited[0][0] = k
		q = deque([(0, 0, k)])
		while q:
			steps += 1
			prev_min = min_steps
			for _ in range(len(q)):
				(r, c, p) = q.popleft()
				for (dx, dy) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
					(x, y) = (c + dx, r + dy)
					if x < 0 or x >= cols or y < 0 or (y >= rows):
						continue
					kk = p - grid[y][x]
					if kk <= visited[y][x]:
						continue
					to_target = rows - y + cols - x - 2
					if kk >= to_target - 1 and visited[y][x] == -1:
						return steps + to_target
					q.append((y, x, kk))
					visited[y][x] = kk
					min_steps = min(min_steps, to_target)
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if 0 == len(grid) - 1 and 0 == len(grid[0]) - 1:
			return 0
		(m, n) = (len(grid), len(grid[0]))
		if k >= m + n - 3:
			return m + n - 2
		seen = set()
		q = collections.deque()
		q.append((0, 0, k))
		seen.add((0, 0, k))
		steps = 0
		direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		while q:
			for i in range(len(q)):
				(r, c, k) = q.popleft()
				for (x, y) in direction:
					R = r + x
					C = c + y
					if (R, C, k) in seen:
						continue
					if R >= 0 and R < m and (C >= 0) and (C < n):
						if k > 0 and grid[R][C] == 1 and ((R, C, k - 1) not in seen):
							q.append((R, C, k - 1))
							seen.add((R, C, k - 1))
						if grid[R][C] == 0 and (R, C, k) not in seen:
							if R == m - 1 and C == n - 1:
								return steps + 1
							q.append((R, C, k))
							seen.add((R, C, k))
			steps += 1
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if not grid:
			return -1
		onesDict = {(0, 0): 0}
		(m, n) = (len(grid), len(grid[0]))
		heap = [(self.distance(m, n, 0, 0), 0, 0, 0, 0)]
		heapq.heapify(heap)
		while heap:
			(curHue, steps, row, col, ones) = heapq.heappop(heap)
			if (row, col) == (m - 1, n - 1):
				return curHue
			for (y, x) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
				(r, c) = (row + y, col + x)
				if 0 <= r < m and 0 <= c < n:
					totalOnes = ones + grid[r][c]
					if totalOnes < onesDict.get((r, c), k + 1):
						heapq.heappush(heap, (steps + 1 + self.distance(m, n, r, c), steps + 1, r, c, totalOnes))
						onesDict[r, c] = totalOnes
		return -1

	def distance(self, m, n, y, x):
		return m + n - y - x - 2


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		m = len(grid[0])
		n = len(grid)
		seen = set()
		queue = deque([(0, 0, 0, k)])
		while queue:
			(x, y, total, r) = queue.popleft()
			if x == m - 1 and y == n - 1:
				return total
			if x - 1 >= 0 and (x - 1, y, r) not in seen:
				seen.add((x - 1, y, r))
				if grid[y][x - 1] == 0:
					queue.append((x - 1, y, total + 1, r))
				if grid[y][x - 1] == 1 and r > 0:
					queue.append((x - 1, y, total + 1, r - 1))
			if x + 1 < m and (x + 1, y, r) not in seen:
				seen.add((x + 1, y, r))
				if grid[y][x + 1] == 0:
					queue.append((x + 1, y, total + 1, r))
				if grid[y][x + 1] == 1 and r > 0:
					queue.append((x + 1, y, total + 1, r - 1))
			if y - 1 >= 0 and (x, y - 1, r) not in seen:
				seen.add((x, y - 1, r))
				if grid[y - 1][x] == 0:
					queue.append((x, y - 1, total + 1, r))
				if grid[y - 1][x] == 1 and r > 0:
					queue.append((x, y - 1, total + 1, r - 1))
			if y + 1 < n and (x, y + 1, r) not in seen:
				seen.add((x, y + 1, r))
				if grid[y + 1][x] == 0:
					queue.append((x, y + 1, total + 1, r))
				if grid[y + 1][x] == 1 and r > 0:
					queue.append((x, y + 1, total + 1, r - 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		q = collections.deque([(0, 0, k)])
		visited = set((0, 0, k))
		dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		step = 0
		while q:
			for _ in range(len(q)):
				(i, j, ck) = q.popleft()
				if i == m - 1 and j == n - 1:
					return step
				for d in dirs:
					(ni, nj) = (i + d[0], j + d[1])
					if ni >= 0 and ni < m and (nj >= 0) and (nj < n) and ((ni, nj, ck) not in visited):
						if grid[ni][nj] == 0:
							q.append((ni, nj, ck))
							visited.add((ni, nj, ck))
						if grid[ni][nj] == 1 and ck > 0 and ((ni, nj, ck - 1) not in visited):
							q.append((ni, nj, ck - 1))
							visited.add((ni, nj, ck - 1))
			step += 1
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		dx = [-1, 1, 0, 0]
		dy = [0, 0, -1, 1]
		queue = collections.deque([(0, 0, 0, k)])
		seen = set([(0, 0, k)])
		while queue:
			(x, y, steps, k) = queue.popleft()
			if x == m - 1 and y == n - 1:
				return steps
			for d in range(4):
				(nxt_x, nxt_y) = (x + dx[d], y + dy[d])
				if (nxt_x, nxt_y, k) not in seen and nxt_x >= 0 and (nxt_x < m) and (nxt_y >= 0) and (nxt_y < n):
					if grid[nxt_x][nxt_y] == 0:
						queue.append((nxt_x, nxt_y, steps + 1, k))
						seen.add((nxt_x, nxt_y, k))
					elif k > 0 and (nxt_x, nxt_y, k - 1) not in seen:
						queue.append((nxt_x, nxt_y, steps + 1, k - 1))
						seen.add((nxt_x, nxt_y, k - 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n, visited) = (len(grid), len(grid[0]), set())
		ds = [(1, 0), (0, 1), (-1, 0), (0, -1)]
		q = collections.deque()
		q.append((0, 0, k))
		visited.add((0, 0, k))
		(res, cnt, total) = (0, 0, 1)
		while q:
			(i, j, r) = q.popleft()
			cnt += 1
			if i == m - 1 and j == n - 1:
				return res
			for d in ds:
				(ni, nj) = (i + d[0], j + d[1])
				if ni >= 0 and ni < m and (nj >= 0) and (nj < n) and ((ni, nj, r) not in visited):
					if grid[ni][nj] == 0 and (ni, nj, r) not in visited:
						visited.add((ni, nj, r))
						q.append((ni, nj, r))
					elif r > 0 and (ni, nj, r - 1) not in visited:
						visited.add((ni, nj, r - 1))
						q.append((ni, nj, r - 1))
			if cnt == total:
				(cnt, total) = (0, len(q))
				res += 1
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(nrow, ncol) = (len(grid), len(grid[0]))
		q = collections.deque([(0, 0, 0, k)])
		visited = set()
		visited.add((0, 0, k))
		while q:
			(i, j, d, life) = q.popleft()
			if i == nrow - 1 and j == ncol - 1:
				return d
			if grid[i][j] == 1:
				if life == 0:
					continue
				else:
					life -= 1
			for (x, y) in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
				if 0 <= x < nrow and 0 <= y < ncol and ((x, y, life) not in visited):
					q.append((x, y, d + 1, life))
					visited.add((x, y, life))
		return -1


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		if m == n == 1:
			return 0
		memo = [[-1] * n for _ in range(m)]
		queue = deque()
		queue.append((0, 0, k, 0))
		visited = set()
		visited.add((0, 0, k))
		while queue:
			(x, y, rem, res) = queue.popleft()
			if rem < 0:
				continue
			for (i, j) in ((x + 1, y), (x - 1, y), (x, y - 1), (x, y + 1)):
				if 0 <= i < m and 0 <= j < n and ((i, j, rem) not in visited):
					if i == m - 1 and j == n - 1:
						return res + 1
					visited.add((i, j, rem))
					if grid[i][j] == 0:
						queue.append((i, j, rem, res + 1))
					else:
						queue.append((i, j, rem - 1, res + 1))
		return -1


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if len(grid) == 1 and len(grid[0]) == 1:
			return 0
		if k > len(grid) - 1 + len(grid[0]) - 1:
			return len(grid) - 1 + len(grid[0]) - 1
		queue = deque([(0, 0, k, 0)])
		visited = set((0, 0, k))
		directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
		while queue:
			(row, col, k, step) = queue.popleft()
			for d in directions:
				x = row + d[0]
				y = col + d[1]
				if x >= 0 and x < len(grid) and (y >= 0) and (y < len(grid[0])):
					if grid[x][y] == 1 and k > 0 and ((x, y, k - 1) not in visited):
						if x == len(grid) - 1 and y == len(grid[0]) - 1:
							return step + 1
						visited.add((x, y, k - 1))
						queue.append((x, y, k - 1, step + 1))
					if grid[x][y] == 0 and (x, y, k) not in visited:
						if x == len(grid) - 1 and y == len(grid[0]) - 1:
							return step + 1
						visited.add((x, y, k))
						queue.append((x, y, k, step + 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		row = len(grid)
		col = len(grid[0])
		queue = []
		queue.append((0, 0, k, 0))
		visited = set()
		visited.add((0, 0, k))
		dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		while queue:
			(r, c, ob, step) = queue.pop(0)
			if (r, c) == (row - 1, col - 1):
				return step
			if grid[r][c] == 1:
				if ob == 0:
					continue
				else:
					ob -= 1
			for (dr, dc) in dirs:
				nr = r + dr
				nc = c + dc
				if (nr, nc, ob) in visited:
					continue
				if not 0 <= nr < row:
					continue
				if not 0 <= nc < col:
					continue
				queue.append((nr, nc, ob, step + 1))
				visited.add((nr, nc, ob))
				pass
			pass
		return -1


import collections

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		self.g = grid
		q = collections.deque()
		dist = {(0, 0): [0] * (k + 1)}
		minDist = {(0, 0): 0}
		q.append((0, 0, 0))
		target = (len(grid) - 1, len(grid[0]) - 1)
		while q:
			node = q.popleft()
			nodeDist = dist[node[0], node[1]][node[2]]
			for n in self.neigh(node):
				nk = node[2] + (1 if grid[n[0]][n[1]] == 1 else 0)
				if n not in dist:
					dist[n] = [None] * (k + 1)
				if nk <= k and dist[n][nk] is None:
					neighDist = nodeDist + 1
					found = False
					for i in range(0, nk):
						if dist[n][i] is not None and dist[n][i] <= neighDist:
							found = True
					if not found:
						dist[n][nk] = nodeDist + 1
						minDist[n] = min(minDist[n], dist[n][nk]) if n in minDist else dist[n][nk]
						q.append((n[0], n[1], nk))
		return minDist[target] if target in minDist else -1

	def neigh(self, pos):
		cand = [(pos[0] + 1, pos[1]), (pos[0] - 1, pos[1]), (pos[0], pos[1] + 1), (pos[0], pos[1] - 1)]
		out = []
		for c in cand:
			if c[0] >= 0 and c[0] < len(self.g) and (c[1] >= 0) and (c[1] < len(self.g[0])):
				out.append(c)
		return out


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if not grid:
			return 0
		nr = len(grid)
		nc = len(grid[0])
		seen = set()
		if grid[0][0] == 0:
			start = (0, 0, k)
		elif grid[0][0] == 1:
			start = (0, 0, k - 1)
		seen.add(start)
		curr_level = [start]
		level = 0
		while curr_level:
			next_level = []
			for (r, c, ob) in curr_level:
				if r == nr - 1 and c == nc - 1:
					return level
				for (dr, dc) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
					(new_r, new_c) = (r + dr, c + dc)
					if 0 <= new_r < nr and 0 <= new_c < nc:
						if grid[new_r][new_c] == 1:
							if ob == 0:
								continue
							new_item = (new_r, new_c, ob - 1)
							if new_item not in seen:
								seen.add(new_item)
								next_level.append(new_item)
						else:
							new_item = (new_r, new_c, ob)
							if new_item not in seen:
								seen.add(new_item)
								next_level.append(new_item)
			curr_level = next_level
			level += 1
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		initial_state = (0, 0, k)
		q = collections.deque()
		q.append(initial_state)
		visited = set()
		visited.add(initial_state)
		dist = 0
		directions = ((-1, 0), (1, 0), (0, -1), (0, 1))
		while q:
			for _ in range(len(q)):
				(i, j, r) = q.popleft()
				if r < 0:
					continue
				if i == m - 1 and j == n - 1:
					return dist
				for (dx, dy) in directions:
					(nx, ny) = (i + dx, j + dy)
					if 0 <= nx < m and 0 <= ny < n:
						if grid[nx][ny] == 0:
							next_state = (nx, ny, r)
						else:
							next_state = (nx, ny, r - 1)
						if next_state not in visited:
							q.append(next_state)
							visited.add(next_state)
			dist += 1
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		queue = collections.deque([(0, 0, 0, 0)])
		m = len(grid)
		n = len(grid[0])
		visited = {}
		visited[0, 0] = 0
		steps = 0
		while queue:
			(x, y, used_k, steps) = queue.popleft()
			if x == m - 1 and y == n - 1:
				return steps
			for (i, j) in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
				(nx, ny) = (x + i, y + j)
				if 0 <= nx < m and 0 <= ny < n:
					if visited.get((nx, ny), float('inf')) <= used_k:
						continue
					if used_k >= k:
						if grid[nx][ny] == 1:
							continue
						else:
							visited[nx, ny] = used_k
							queue.append([nx, ny, used_k, steps + 1])
					elif grid[nx][ny] == 1:
						visited[nx, ny] = used_k + 1
						queue.append([nx, ny, used_k + 1, steps + 1])
					else:
						visited[nx, ny] = used_k
						queue.append([nx, ny, used_k, steps + 1])
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		q = [(0, 0, k, 0)]
		(m, n) = (len(grid), len(grid[0]))
		visited = {(0, 0, k)}
		while q:
			(r, c, ob, step) = q.pop(0)
			if (r, c) == (m - 1, n - 1):
				return step
			if grid[r][c] == 1:
				if ob == 0:
					continue
				else:
					ob -= 1
			for (dr, dc) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
				(nr, nc) = (r + dr, c + dc)
				if 0 <= nr < m and 0 <= nc < n and ((nr, nc, ob) not in visited):
					q.append((nr, nc, ob, step + 1))
					visited.add((nr, nc, ob))
		return -1


import collections

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		move = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		queue = collections.deque([(0, 0, k)])
		seen = set([(0, 0, k)])
		level = 0
		while queue:
			size = len(queue)
			for _ in range(size):
				(x, y, remain) = queue.popleft()
				if x == m - 1 and y == n - 1:
					return level
				for (dx, dy) in move:
					(newX, newY) = (x + dx, y + dy)
					if 0 <= newX < m and 0 <= newY < n:
						if grid[newX][newY] == 0:
							if (newX, newY, remain) not in seen:
								queue.append((newX, newY, remain))
								seen.add((newX, newY, remain))
						elif remain > 0:
							if (newX, newY, remain - 1) not in seen:
								queue.append((newX, newY, remain - 1))
								seen.add((newX, newY, remain - 1))
			level += 1
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(N, M) = (len(grid), len(grid[0]))
		moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
		queue = [(N - 1, M - 1, k, 0)]
		visited = set([(N - 1, M - 1, k)])
		for (i, j, k, m) in queue:
			if i == 0 and j == 0:
				return m
			for move in moves:
				(ni, nj) = (i + move[0], j + move[1])
				if N > ni >= 0 <= nj < M:
					nk = k - grid[ni][nj]
					if nk >= 0 and (ni, nj, nk) not in visited:
						visited.add((ni, nj, nk))
						queue.append((ni, nj, nk, m + 1))
		return -1


import collections

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		queue = collections.deque()
		queue.append([0, 0, k, 0])
		visited = set((0, 0, k))
		while queue:
			(x, y, k, step) = queue.popleft()
			if x == m - 1 and y == n - 1:
				return step
			for (nx, ny) in ((x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)):
				if 0 <= nx < m and 0 <= ny < n:
					nk = k - grid[nx][ny]
					if nk >= 0 and (not (nx, ny, nk) in visited):
						visited.add((nx, ny, nk))
						queue.append((nx, ny, nk, step + 1))
		return -1


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		dq = deque()
		dq.append((0, 0, k, 0))
		visited = set()
		visited.add((0, 0, k))
		while dq:
			cur = dq.popleft()
			row = cur[0]
			col = cur[1]
			elm = cur[2]
			pth = cur[3]
			if row == len(grid) - 1 and col == len(grid[0]) - 1:
				return pth
			if col < len(grid[0]) - 1:
				if grid[row][col + 1] == 1:
					if elm > 0 and (row, col + 1, elm - 1) not in visited:
						dq.append((row, col + 1, elm - 1, pth + 1))
						visited.add((row, col + 1, elm - 1))
				elif (row, col + 1, elm) not in visited:
					dq.append((row, col + 1, elm, pth + 1))
					visited.add((row, col + 1, elm))
			if row < len(grid) - 1:
				if grid[row + 1][col] == 1:
					if elm > 0 and (row + 1, col, elm - 1) not in visited:
						dq.append((row + 1, col, elm - 1, pth + 1))
						visited.add((row + 1, col, elm - 1))
				elif (row + 1, col, elm) not in visited:
					dq.append((row + 1, col, elm, pth + 1))
					visited.add((row + 1, col, elm))
			if row > 0:
				if grid[row - 1][col] == 1:
					if elm > 0 and (row - 1, col, elm - 1) not in visited:
						dq.append((row - 1, col, elm - 1, pth + 1))
						visited.add((row - 1, col, elm - 1, pth + 1))
				elif (row - 1, col, elm) not in visited:
					dq.append((row - 1, col, elm, pth + 1))
					visited.add((row - 1, col, elm))
			if col > 0:
				if grid[row][col - 1] == 1:
					if elm > 0 and (row, col - 1, elm - 1) not in visited:
						dq.append((row, col - 1, elm - 1, pth + 1))
						visited.add((row, col - 1, elm - 1))
					elif (row, col - 1, elm) not in visited:
						dq.append((row, col - 1, elm, pth + 1))
						visited.add((row, col - 1, elm))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		q = deque([(0, 0, k)])
		visited = set()
		m = len(grid)
		n = len(grid[0])
		res = 0
		while q:
			l = len(q)
			for _ in range(l):
				(i, j, k) = q.popleft()
				if i == m - 1 and j == n - 1:
					return res
				for (ii, jj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
					if 0 <= ii < m and 0 <= jj < n:
						if grid[ii][jj] == 0:
							if (ii, jj, k) not in visited:
								visited.add((ii, jj, k))
								q.append((ii, jj, k))
						elif k > 0 and (ii, jj, k - 1) not in visited:
							visited.add((ii, jj, k - 1))
							q.append((ii, jj, k - 1))
			res += 1
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		from collections import deque, defaultdict
		moves = [[-1, 0], [1, 0], [0, -1], [0, 1]]
		rows = len(grid)
		cols = len(grid[0])
		seen = set()
		queue = deque()
		queue.append((0, 0, k, 0))
		while len(queue) > 0:
			(row, col, eliminations_left, path_length) = queue.popleft()
			if row == rows - 1 and col == cols - 1:
				return path_length
			for move in moves:
				(next_row, next_col) = (row + move[0], col + move[1])
				if not 0 <= next_row < rows or not 0 <= next_col < cols:
					continue
				if (next_row, next_col, eliminations_left) in seen:
					continue
				if grid[next_row][next_col] == 1:
					if eliminations_left > 0:
						seen.add((next_row, next_col, eliminations_left))
						queue.append((next_row, next_col, eliminations_left - 1, path_length + 1))
				else:
					seen.add((next_row, next_col, eliminations_left))
					queue.append((next_row, next_col, eliminations_left, path_length + 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		nrows = len(grid)
		ncols = len(grid[0])
		if nrows == 1 and ncols == 1:
			return 0
		step = 1
		if k > nrows - 1 + ncols - 1:
			return nrows - 1 + ncols - 1
		q = collections.deque()
		visited = set([(0, 0, k)])
		q.append((0, 0, k, step))

		def neigh(x, y):
			tocheck = [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]
			nlist = []
			for n in tocheck:
				if 0 <= n[0] < nrows and 0 <= n[1] < ncols:
					nlist.append(n)
			return nlist
		while q:
			(i, j, k, step) = q.popleft()
			neighs = neigh(i, j)
			if i == nrows - 1 and j == ncols - 1:
				return step
			if neighs:
				for n in neighs:
					if grid[n[0]][n[1]] == 1 and k > 0 and ((n[0], n[1], k - 1) not in visited):
						q.append((n[0], n[1], k - 1, step + 1))
						visited.add((n[0], n[1], k - 1))
					if grid[n[0]][n[1]] == 0 and (n[0], n[1], k) not in visited:
						if n[0] == nrows - 1 and n[1] == ncols - 1:
							return step
						q.append((n[0], n[1], k, step + 1))
						visited.add((n[0], n[1], k))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		start = (0, 0, k)
		queue = collections.deque([(0, start)])
		visited = set([start])
		while queue:
			(steps, (i, j, k)) = queue.popleft()
			if i == m - 1 and j == n - 1:
				return steps
			for (dx, dy) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
				(x, y) = (i + dx, j + dy)
				if 0 <= x < m and 0 <= y < n:
					state = (x, y, k - grid[x][y])
					if state not in visited and state[2] >= 0:
						queue.append((steps + 1, state))
						visited.add(state)
		return -1


class Solution:
	from collections import deque

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		D = [[-1, 0], [1, 0], [0, 1], [0, -1]]
		Q = deque([])
		Q.append((0, 0, k, 0))
		visited = set()
		while Q:
			(x, y, rem, lv) = Q.popleft()
			if x == m - 1 and y == n - 1:
				return lv
			for (dx, dy) in D:
				if 0 <= x + dx < m and 0 <= y + dy < n and ((x + dx, y + dy, rem) not in visited):
					visited.add((x + dx, y + dy, rem))
					if grid[x + dx][y + dy] == 0:
						Q.append((x + dx, y + dy, rem, lv + 1))
					elif grid[x + dx][y + dy] == 1 and rem > 0:
						Q.append((x + dx, y + dy, rem - 1, lv + 1))
		return -1


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if len(grid) == 1 and len(grid[0]) == 1:
			return 0
		queue = deque([(0, 0, k, 0)])
		directions = [[0, 1], [0, -1], [-1, 0], [1, 0]]
		visited = set([(0, 0, k)])
		(M, N) = (len(grid), len(grid[0]))
		while queue:
			(i, j, m, steps) = queue.popleft()
			for (dx, dy) in directions:
				x = dx + i
				y = dy + j
				if 0 <= x < M and 0 <= y < N:
					if grid[x][y] == 1 and m > 0 and ((x, y, m - 1) not in visited):
						visited.add((x, y, m - 1))
						queue.append((x, y, m - 1, steps + 1))
					if grid[x][y] == 0 and (x, y, m) not in visited:
						if x == M - 1 and y == N - 1:
							return steps + 1
						visited.add((x, y, m))
						queue.append((x, y, m, steps + 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if not grid:
			return -1
		(m, n, direction) = (len(grid), len(grid[0]), [[0, 1], [0, -1], [1, 0], [-1, 0]])
		visited = [[[False] * (k + 1) for _ in range(n)] for _ in range(m)]
		visited[0][0][0] = True
		(count, queue) = (0, deque([[0, 0, 0]]))
		while len(queue) > 0:
			size = len(queue)
			for i in range(size):
				cur = queue.popleft()
				if cur[0] == m - 1 and cur[1] == n - 1:
					return count
				for d in direction:
					(r, c, tmpK) = (cur[0] + d[0], cur[1] + d[1], cur[2])
					if r >= 0 and c >= 0 and (r < m) and (c < n):
						if grid[r][c] == 1:
							tmpK += 1
						if tmpK <= k and (not visited[r][c][tmpK]):
							visited[r][c][tmpK] = True
							queue.append([r, c, tmpK])
			count += 1
		return -1


from collections import deque
dirs = [(0, -1), (0, 1), (-1, 0), (1, 0)]

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		dq = deque([(0, 0, k)])
		visited = set([(0, 0, k)])
		step = 0
		while dq:
			size = len(dq)
			for i in range(size):
				(r, c, p) = dq.popleft()
				if r == m - 1 and c == n - 1:
					return step
				for d in dirs:
					(nr, nc) = (r + d[0], c + d[1])
					if not 0 <= nr < m or not 0 <= nc < n:
						continue
					elif grid[nr][nc] == 0:
						if (nr, nc, p) not in visited:
							visited.add((nr, nc, p))
							dq.append((nr, nc, p))
					elif grid[nr][nc] == 1:
						if p > 0 and (nr, nc, p - 1) not in visited:
							visited.add((nr, nc, p - 1))
							dq.append((nr, nc, p - 1))
			step += 1
		return -1


class Solution:

	def shortestPath(self, grid, k):
		if not grid or not grid[0]:
			return -1
		n = len(grid)
		m = len(grid[0])
		q = [[0, 0, 0, k]]
		seen = set()
		seen.add((0, 0, k))
		while q:
			(d, r, c, ob) = q.pop(0)
			if r == n - 1 and c == m - 1:
				return d
			if grid[r][c] == 1:
				if ob == 0:
					continue
				ob -= 1
			for (dr, dc) in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
				nr = r + dr
				nc = c + dc
				if 0 <= nr < n and 0 <= nc < m:
					if (nr, nc, ob) in seen:
						continue
					q.append([d + 1, nr, nc, ob])
					seen.add((nr, nc, ob))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if len(grid) == 1 and len(grid[0]) == 1:
			return 0
		q = collections.deque([(0, 0, 0, 0)])
		(m, n) = (len(grid), len(grid[0]))
		visited = set()
		while q:
			(x, y, obstacle, path) = q.popleft()
			for (i, j) in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
				if 0 <= i < m and 0 <= j < n:
					if grid[i][j] == 1 and obstacle < k and ((i, j, obstacle + 1) not in visited):
						visited.add((i, j, obstacle + 1))
						q.append((i, j, obstacle + 1, path + 1))
					if grid[i][j] == 0 and (i, j, obstacle) not in visited:
						if (i, j) == (m - 1, n - 1):
							return path + 1
						visited.add((i, j, obstacle))
						q.append((i, j, obstacle, path + 1))
		return -1


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		rowlen = len(grid)
		collen = len(grid[0])
		if k > len(grid) - 1 + len(grid[0]) - 1:
			return len(grid) - 1 + len(grid[0]) - 1
		visited = set()
		visited.add((0, 0, k))
		q = deque([(0, 0, k, 0)])

		def get_nexts(x, y):
			return [(nx, ny) for (nx, ny) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)] if 0 <= nx < rowlen and 0 <= ny < collen]
		while q:
			(x, y, k, path_count) = q.popleft()
			if (x, y) == (rowlen - 1, collen - 1):
				return path_count
			nexts = get_nexts(x, y)
			for (nx, ny) in nexts:
				if grid[nx][ny] == 1 and (not k):
					continue
				if grid[nx][ny] == 1 and (nx, ny, k - 1) in visited:
					continue
				if grid[nx][ny] == 0 and (nx, ny, k) in visited:
					continue
				if grid[nx][ny] == 1:
					visited.add((nx, ny, k - 1))
					q.append((nx, ny, k - 1, path_count + 1))
				else:
					if (nx, ny) == (rowlen - 1, collen - 1):
						return path_count + 1
					visited.add((nx, ny, k))
					q.append((nx, ny, k, path_count + 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(HT, WT) = (len(grid), len(grid[0]))
		TARGET = (HT - 1, WT - 1)
		from collections import deque
		q = deque([(0, 0, k)])
		visited = set(q)
		lvl_cnt = 0
		while q:
			for i in range(len(q)):
				(r, c, new_k) = q.popleft()
				if (r, c) == TARGET:
					return lvl_cnt
				for (i, j) in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
					if 0 <= i < HT and 0 <= j < WT:
						if grid[i][j] == 0 and (i, j, new_k) not in visited:
							q.append((i, j, new_k))
							visited.add((i, j, new_k))
						elif grid[i][j] == 1 and new_k > 0 and ((i, j, new_k - 1) not in visited):
							q.append((i, j, new_k - 1))
							visited.add((i, j, new_k - 1))
			lvl_cnt += 1
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if len(grid) == 1 and len(grid[0]) == 1:
			return int()
		queue = collections.deque([(0, 0, 0, 0)])
		(row, col) = (len(grid), len(grid[0]))
		visited = set()
		while queue:
			(x, y, obstacle, path) = queue.popleft()
			for (i, j) in ((x + 1, y), (x - 1, y), (x, y - 1), (x, y + 1)):
				if 0 <= i < row and 0 <= j < col:
					if grid[i][j] == 1 and obstacle < k and ((i, j, obstacle + 1) not in visited):
						visited.add((i, j, obstacle + 1))
						queue.append((i, j, obstacle + 1, path + 1))
					elif grid[i][j] == 0 and (i, j, obstacle) not in visited:
						if i == row - 1 and j == col - 1:
							return path + 1
						visited.add((i, j, obstacle))
						queue.append((i, j, obstacle, path + 1))
		return -1


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		queue = deque([(0, 0, 0, 0)])
		visited = set()
		visited.add((0, 0, 0))
		m = len(grid)
		n = len(grid[0])
		directions = [(0, -1), (-1, 0), (0, 1), (1, 0)]
		while queue:
			(r, c, removed, count) = queue.popleft()
			if r == m - 1 and c == n - 1:
				return count
			for (inc_r, inc_c) in directions:
				new_r = r + inc_r
				new_c = c + inc_c
				if 0 <= new_r < m and 0 <= new_c < n:
					if removed < k and (new_r, new_c, removed + 1) not in visited and (grid[new_r][new_c] == 1):
						queue.append((new_r, new_c, removed + 1, count + 1))
						visited.add((new_r, new_c, removed + 1))
					elif (new_r, new_c, removed) not in visited and grid[new_r][new_c] == 0:
						queue.append((new_r, new_c, removed, count + 1))
						visited.add((new_r, new_c, removed))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if len(grid) == 1 and len(grid[0]) == 1:
			return 0
		visited = set()
		q = collections.deque([(0, 0, 0, 0)])
		(r, c) = (len(grid), len(grid[0]))
		while q:
			(x, y, obs, path) = q.popleft()
			for (i, j) in [(x, y + 1), (x, y - 1), (x + 1, y), (x - 1, y)]:
				if 0 <= i < r and 0 <= j < c:
					if grid[i][j] == 0 and (i, j, obs) not in visited:
						if i == r - 1 and j == c - 1:
							return path + 1
						q.append([i, j, obs, path + 1])
						visited.add((i, j, obs))
					if grid[i][j] == 1 and obs < k and ((i, j, obs + 1) not in visited):
						q.append([i, j, obs + 1, path + 1])
						visited.add((i, j, obs + 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		q = deque([(0, 0, k)])
		visited = set([(0, 0, k)])
		steps = 0
		while q:
			size = len(q)
			for _ in range(size):
				(i, j, remain) = q.popleft()
				if (i, j) == (m - 1, n - 1):
					return steps
				for (x, y) in ((i, j - 1), (i - 1, j), (i, j + 1), (i + 1, j)):
					if m > x >= 0 <= y < n:
						if grid[x][y] == 0 and (x, y, remain) not in visited:
							q.append((x, y, remain))
							visited.add((x, y, remain))
						elif grid[x][y] == 1 and remain > 0 and ((x, y, remain - 1) not in visited):
							q.append((x, y, remain - 1))
							visited.add((x, y, remain - 1))
			steps += 1
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		K = k
		q = []
		q.append((0, 0, K, 0))
		seen = set()
		while q:
			q2 = []
			for (i, j, k, c) in q:
				if i == m - 1 and j == n - 1:
					return c
				for (ii, jj) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
					if 0 <= ii < m and 0 <= jj < n:
						if grid[ii][jj] == 0 and (ii, jj, k) not in seen:
							seen.add((ii, jj, k))
							q2.append((ii, jj, k, c + 1))
						if grid[ii][jj] == 1 and k > 0 and ((ii, jj, k - 1) not in seen):
							seen.add((ii, jj, k - 1))
							q2.append((ii, jj, k - 1, c + 1))
			q = q2
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if len(grid) == 1 and len(grid[0]) == 1:
			return 0
		queue = deque([(0, 0, k, 0)])
		visited = set([(0, 0, k)])
		while queue:
			(row, col, eliminate, steps) = queue.popleft()
			for (new_row, new_col) in [(row - 1, col), (row, col + 1), (row + 1, col), (row, col - 1)]:
				if new_row >= 0 and new_row < len(grid) and (new_col >= 0) and (new_col < len(grid[0])):
					if grid[new_row][new_col] == 1 and eliminate > 0 and ((new_row, new_col, eliminate - 1) not in visited):
						visited.add((new_row, new_col, eliminate - 1))
						queue.append((new_row, new_col, eliminate - 1, steps + 1))
					if grid[new_row][new_col] == 0 and (new_row, new_col, eliminate) not in visited:
						if new_row == len(grid) - 1 and new_col == len(grid[0]) - 1:
							return steps + 1
						visited.add((new_row, new_col, eliminate))
						queue.append((new_row, new_col, eliminate, steps + 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		d = deque([(0, 0, k)])
		visited = {(0, 0, k)}

		def get_neigbour(x, y, z):
			for (x0, y0) in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
				if 0 <= x0 < m and 0 <= y0 < n:
					z0 = z - grid[x0][y0]
					if z0 >= 0:
						yield (x0, y0, z0)
		steps = 0
		while d:
			size = len(d)
			for i in range(size):
				(x, y, z) = d.popleft()
				if (x, y) == (m - 1, n - 1):
					return steps
				for nxt in get_neigbour(x, y, z):
					if nxt in visited:
						continue
					visited.add(nxt)
					d.append(nxt)
			steps += 1
		return -1


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		q = deque()
		cur = (0, 0, k, 0)
		visited = set()
		q.append(cur)
		visited.add(cur)
		m = len(grid)
		n = len(grid[0])
		diffs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		while len(q) != 0:
			(i, j, l, s) = q.popleft()
			if i == m - 1 and j == n - 1:
				return s
			for d in diffs:
				n_i = i + d[0]
				n_j = j + d[1]
				if 0 <= n_i < m and 0 <= n_j < n:
					if grid[n_i][n_j] and l != 0 and ((n_i, n_j, l - 1) not in visited):
						q.append((n_i, n_j, l - 1, s + 1))
						visited.add((n_i, n_j, l - 1))
					elif not grid[n_i][n_j] and (n_i, n_j, l) not in visited:
						q.append((n_i, n_j, l, s + 1))
						visited.add((n_i, n_j, l))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(r, c) = (len(grid), len(grid[0]))
		if r == 1 and c == 1:
			return 0
		q = deque([(0, 0, 0, 0)])
		visited = set((0, 0, 0))
		while q:
			(row, col, met, step) = q.popleft()
			if met > k:
				continue
			for (nr, nc) in [[row + 1, col], [row - 1, col], [row, col + 1], [row, col - 1]]:
				if 0 <= nr < r and 0 <= nc < c:
					if grid[nr][nc] == 1 and met < k and ((nr, nc, met + 1) not in visited):
						visited.add((nr, nc, met + 1))
						q.append((nr, nc, met + 1, step + 1))
					if grid[nr][nc] == 0 and (nr, nc, met) not in visited:
						if (nr, nc) == (r - 1, c - 1):
							return step + 1
						visited.add((nr, nc, met))
						q.append((nr, nc, met, step + 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		n = len(grid)
		m = len(grid[0])
		queue = [(0, 0, k)]
		step = 0
		ds = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		visited = {(0, 0, k)}
		if n == 1 and m == 1:
			return 0
		while queue:
			tmp = queue
			queue = []
			for (i, j, eliminate) in tmp:
				for d in ds:
					x = i + d[0]
					y = j + d[1]
					if x == n - 1 and y == m - 1:
						return step + 1
					if x >= 0 and x < n and (y >= 0) and (y < m):
						if grid[x][y] == 0 and (x, y, eliminate) not in visited:
							visited.add((x, y, eliminate))
							queue.append((x, y, eliminate))
						elif grid[x][y] == 1 and eliminate >= 1 and ((x, y, eliminate - 1) not in visited):
							visited.add((x, y, eliminate - 1))
							queue.append((x, y, eliminate - 1))
			step += 1
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if not grid:
			return 0
		queue = collections.deque([(0, 0, k, 0)])
		(r, c) = (len(grid), len(grid[0]))
		visited = set()
		direction = []
		while queue:
			(x, y, eliminate, steps) = queue.popleft()
			if x == r - 1 and y == c - 1:
				return steps
			for (nx, ny) in ((x + 1, y), (x - 1, y), (x, y - 1), (x, y + 1)):
				if nx >= 0 and nx < r and (ny >= 0) and (ny < c):
					if eliminate > 0 and (nx, ny, eliminate - 1) not in visited and (grid[nx][ny] == 1):
						queue.append((nx, ny, eliminate - 1, steps + 1))
						visited.add((nx, ny, eliminate - 1))
					if (nx, ny, eliminate) not in visited and grid[nx][ny] == 0:
						queue.append((nx, ny, eliminate, steps + 1))
						visited.add((nx, ny, eliminate))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(n, m) = (len(grid), len(grid[0]))
		bfs = collections.deque([(0, 0, 0, 0)])
		seen = set([(0, 0, 0)])
		while bfs:
			(c, used, i, j) = bfs.popleft()
			if i == n - 1 and j == m - 1:
				return c
			for (ni, nj) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
				if 0 <= ni < n and 0 <= nj < m and (used + grid[ni][nj] <= k) and ((ni, nj, used + grid[ni][nj]) not in seen):
					bfs.append((c + 1, used + grid[ni][nj], ni, nj))
					seen.add((ni, nj, used + grid[ni][nj]))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		queue = [(0, 0, k)]
		direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]
		h = len(grid)
		w = len(grid[0])
		step = 0
		if h == 1 and w == 1:
			return 0
		visited = {}
		while queue:
			target = {}
			step += 1
			for (y0, x0, r) in queue:
				for (y_offset, x_offset) in direction:
					y1 = y0 + y_offset
					x1 = x0 + x_offset
					if 0 <= y1 < h and 0 <= x1 < w:
						if y1 == h - 1 and x1 == w - 1:
							return step
						if (y1, x1) in visited:
							if visited[y1, x1] >= r:
								continue
						if grid[y1][x1] == 0:
							visited[y1, x1] = r
							target[y1, x1] = max(target.get((y1, x1), r), r)
						elif r > 0:
							visited[y1, x1] = r - 1
							target[y1, x1] = max(target.get((y1, x1), r - 1), r - 1)
			queue = [(k[0], k[1], v) for (k, v) in target.items()]
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		visited = set()
		directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
		queue = [(0, 0, 0)]
		steps = 0
		while queue:
			new_q = []
			for (x, y, r) in queue:
				if x == len(grid) - 1 and y == len(grid[0]) - 1:
					return steps
				for (ix, iy) in directions:
					xx = x + ix
					yy = y + iy
					if xx >= 0 and xx < len(grid) and (yy >= 0) and (yy < len(grid[0])):
						rr = r + (1 if grid[xx][yy] == 1 else 0)
						if (xx, yy, rr) not in visited and rr <= k:
							visited.add((xx, yy, rr))
							new_q.append((xx, yy, rr))
			steps += 1
			queue = new_q
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(r, c) = (len(grid), len(grid[0]))
		qu = deque([[0, 0, 0, 0]])
		visited = set()
		while qu:
			(i, j, cnt, length) = qu.popleft()
			visited.add((i, j, cnt))
			if (i, j) == (r - 1, c - 1):
				return length
			for (x, y) in [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]]:
				if 0 <= x < r and 0 <= y < c:
					new_cnt = cnt if grid[x][y] == 0 else cnt + 1
					if new_cnt <= k and (x, y, new_cnt) not in visited:
						visited.add((x, y, new_cnt))
						qu.append([x, y, new_cnt, length + 1])
		return -1
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		queue = []
		queue.append((0, 0, 0, 0))
		visited = set()
		visited.add((0, 0, 0))
		while queue:
			(i, j, obstacles_used, length) = queue.pop(0)
			if i == len(grid) - 1 and j == len(grid[0]) - 1:
				return length
			directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
			for (a, b) in directions:
				newi = i + a
				newj = j + b
				if newi >= 0 and newi < len(grid) and (newj >= 0) and (newj < len(grid[0])):
					newObstacles = obstacles_used + grid[newi][newj]
					if newObstacles <= k and (newi, newj, newObstacles) not in visited:
						visited.add((newi, newj, newObstacles))
						queue.append((newi, newj, newObstacles, length + 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		q = collections.deque([(0, 0, 0, k)])
		vis = set([(0, 0, k)])
		while q:
			(x, y, s, r) = q.popleft()
			if x == len(grid) - 1 and y == len(grid[0]) - 1:
				return s
			for (i, j) in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
				if 0 <= i < len(grid) and 0 <= j < len(grid[0]):
					if grid[i][j] == 1 and r > 0 and ((i, j, r - 1) not in vis):
						vis.add((i, j, r - 1))
						q.append((i, j, s + 1, r - 1))
					if grid[i][j] == 0 and (i, j, r) not in vis:
						vis.add((i, j, r))
						q.append((i, j, s + 1, r))
		return -1


from collections import defaultdict, deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:

		def getNei(x, y):
			for (dx, dy) in dirs:
				(xn, yn) = (x + dx, y + dy)
				if 0 <= xn < M and 0 <= yn < N:
					yield (xn, yn)
		dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]
		(M, N) = (len(grid), len(grid[0]))
		inf_num = float(inf)
		visited = [[[inf_num] * (k + 1) for _ in range(N)] for _ in range(M)]
		queue = deque([(0, 0, k, 0)])
		while queue:
			(i, j, kk, cost) = queue.popleft()
			if i == M - 1 and j == N - 1:
				return cost
			if visited[i][j][kk] < inf:
				continue
			visited[i][j][kk] = cost
			for (x, y) in getNei(i, j):
				if grid[x][y] == 1:
					if kk > 0 and cost + 1 < visited[x][y][kk]:
						queue.append((x, y, kk - 1, cost + 1))
				elif cost + 1 < visited[x][y][kk]:
					queue.append((x, y, kk, cost + 1))
		return -1


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		visited = {}
		queue = deque()
		queue.append([0, 0])
		visited[0, 0] = 0
		step = 0
		offset = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		while queue:
			size = len(queue)
			while size:
				size -= 1
				(x, y) = queue.popleft()
				obs = visited[x, y]
				if x == m - 1 and y == n - 1:
					return step
				for (dx, dy) in offset:
					(nx, ny) = (x + dx, y + dy)
					if 0 <= nx < m and 0 <= ny < n and (nx, ny):
						n_obs = obs + grid[nx][ny]
						if n_obs > k:
							continue
						if (nx, ny) in visited and n_obs < visited[nx, ny]:
							visited[nx, ny] = n_obs
							queue.append((nx, ny))
						elif (nx, ny) not in visited:
							visited[nx, ny] = n_obs
							queue.append((nx, ny))
			step += 1
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if len(grid) == 1 and len(grid[0]) == 1:
			return 0
		q = []
		q.append((0, 0, 0, 0))
		(m, n) = (len(grid), len(grid[0]))
		visited = set()
		while q:
			(x, y, obstacle_eliminated, count) = q.pop(0)
			for (nx, ny) in [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)]:
				if 0 <= nx < m and 0 <= ny < n:
					if (nx, ny) == (m - 1, n - 1):
						return count + 1
					if grid[nx][ny] == 1 and obstacle_eliminated < k and ((nx, ny, obstacle_eliminated + 1) not in visited):
						visited.add((nx, ny, obstacle_eliminated + 1))
						q.append((nx, ny, obstacle_eliminated + 1, count + 1))
					if grid[nx][ny] == 0 and (nx, ny, obstacle_eliminated) not in visited:
						visited.add((nx, ny, obstacle_eliminated))
						q.append((nx, ny, obstacle_eliminated, count + 1))
		return -1


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if grid[0][0] == 1:
			k -= 1
		q = deque([(0, 0, k, 0)])
		visited = set([(0, 0, k)])
		while len(q) > 0:
			(r, c, avail, path) = q.popleft()
			if r == len(grid) - 1 and c == len(grid[0]) - 1:
				return path
			for (dr, dc) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
				(nr, nc) = (r + dr, c + dc)
				if nr < 0 or nr >= len(grid) or nc < 0 or (nc >= len(grid[0])):
					continue
				if grid[nr][nc] == 1 and (not avail):
					continue
				if (nr, nc, avail) in visited:
					continue
				visited.add((nr, nc, avail))
				if grid[nr][nc] == 0:
					q.append((nr, nc, avail, path + 1))
				elif avail > 0:
					q.append((nr, nc, avail - 1, path + 1))
		return -1


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
		q = deque([(0, 0, 0, k)])
		visited = set([(0, 0, k)])
		if len(grid[0]) == 1 and len(grid) == 1:
			return 0
		while q:
			(row, col, dist, cur_k) = q.popleft()
			for (i, j) in directions:
				nr = row + i
				nc = col + j
				d = dist + 1
				if nr < len(grid) and nr >= 0 and (nc < len(grid[0])) and (nc >= 0):
					if (nr, nc, cur_k) not in visited and grid[nr][nc] == 0:
						if nr == len(grid) - 1 and col + j == len(grid[0]) - 1:
							return dist + 1
						q.append((nr, col + j, d, cur_k))
						visited.add((nr, col + j, cur_k))
					if (nr, nc, cur_k - 1) not in visited and grid[nr][nc] == 1:
						if cur_k > 0:
							if nr == len(grid) - 1 and col + j == len(grid[0]) - 1:
								return dist + 1
							q.append((nr, nc, d, cur_k - 1))
							visited.add((nr, nc, cur_k - 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if not grid or grid[0][0] == 1 or grid[-1][-1] == 1:
			return -1
		(r, c) = (len(grid), len(grid[0]))
		dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
		visited = set()
		q = [(0, 0, 0, k)]
		visited.add((0, 0, 0))
		while q:
			(x, y, steps, obs) = q.pop(0)
			if obs < 0:
				continue
			if x == r - 1 and y == c - 1:
				return steps
			for (dx, dy) in dirs:
				(nx, ny) = (x + dx, y + dy)
				if 0 <= nx < r and 0 <= ny < c and (grid[nx][ny] == 0):
					if (nx, ny, obs) not in visited:
						q.append((nx, ny, steps + 1, obs))
						visited.add((nx, ny, obs))
				elif 0 <= nx < r and 0 <= ny < c and (grid[nx][ny] == 1):
					if obs > 0:
						if (nx, ny, obs - 1) not in visited:
							q.append((nx, ny, steps + 1, obs - 1))
							visited.add((nx, ny, obs - 1))
		return -1


from typing import List
from functools import lru_cache
import collections
import heapq
import itertools
import bisect
import copy
import random
import re
import fractions
import math
import functools
mod = 10 ** 9 + 7

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if not len(grid) or not len(grid[0]):
			return 0
		(m, n) = (len(grid), len(grid[0]))

		def neighbors(i, j):
			for (ni, nj) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
				if 0 <= ni < m and 0 <= nj < n:
					yield (ni, nj)
		start = (0, 0, k)
		seen = {start}
		q = collections.deque([(0, start)])
		while q:
			(step, (i, j, k)) = q.popleft()
			if (i, j) == (m - 1, n - 1):
				return step
			for (ni, nj) in neighbors(i, j):
				nk = k - grid[ni][nj]
				state = (ni, nj, nk)
				if nk >= 0 and state not in seen:
					q.append((step + 1, state))
					seen.add(state)
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(length, width) = (len(grid), len(grid[0]))
		que = collections.deque([])
		que.append((0, 0, 0, k))
		visited = set()
		visited.add((0, 0, k))
		directions = ([-1, 0], [0, 1], [1, 0], [0, -1])
		while len(que):
			(x, y, steps, eliminates) = que.popleft()
			if x == length - 1 and y == width - 1:
				return steps
			for (dx, dy) in directions:
				next_x = x + dx
				next_y = y + dy
				if self.isValid(next_x, next_y, grid) and (next_x, next_y, eliminates) not in visited:
					if grid[next_x][next_y] == 1 and eliminates > 0:
						visited.add((next_x, next_y, eliminates))
						que.append((next_x, next_y, steps + 1, eliminates - 1))
					elif grid[next_x][next_y] == 0:
						visited.add((next_x, next_y, eliminates))
						que.append((next_x, next_y, steps + 1, eliminates))
		return -1

	def isValid(self, next_x, next_y, grid):
		if next_x >= 0 and next_x < len(grid) and (next_y >= 0) and (next_y < len(grid[0])):
			return True
		else:
			return False


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:

		def method1():
			R = len(grid)
			if R < 1:
				return -1
			C = len(grid[0])
			seen = set()
			queue = collections.deque([(0, 0, k, 0)])
			seen.add((0, 0, k))

			def neighbors(r, c):
				for (dr, dc) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
					(nr, nc) = (r + dr, c + dc)
					if 0 <= nr < R and 0 <= nc < C:
						yield (nr, nc)
			while queue:
				(r, c, ck, dist) = queue.popleft()
				if r == R - 1 and c == C - 1:
					return dist
				for (nr, nc) in neighbors(r, c):
					newk = ck
					if grid[nr][nc] == 1:
						newk -= 1
						if newk < 0:
							continue
					if (nr, nc, newk) in seen:
						continue
					seen.add((nr, nc, newk))
					queue.append((nr, nc, newk, dist + 1))
			return -1
		return method1()


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		K = k
		q = []
		q.append((0, 0, K, 0))
		seen = set()
		while q:
			q2 = []
			for (i, j, k, c) in q:
				if i == m - 1 and j == n - 1:
					return c
				for (ii, jj) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
					if 0 <= ii < m and 0 <= jj < n:
						if grid[ii][jj] == 0 and (ii, jj, k) not in seen:
							seen.add((ii, jj, k))
							q2.append((ii, jj, k, c + 1))
						if grid[ii][jj] == 1 and k > 0 and ((ii, jj, k - 1) not in seen):
							seen.add((ii, jj, k - 1))
							q2.append((ii, jj, k - 1, c + 1))
			q = q2
		return -1

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		K = k
		q = []
		q.append((0, 0, K, 0))
		seen = {}
		while q:
			q2 = []
			for (i, j, k, c) in q:
				if i == m - 1 and j == n - 1:
					return c
				for (ii, jj) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
					if 0 <= ii < m and 0 <= jj < n:
						if grid[ii][jj] == 0 and ((ii, jj) not in seen or k > seen[ii, jj]):
							seen[ii, jj] = k
							q2.append((ii, jj, k, c + 1))
						if grid[ii][jj] == 1 and k > 0 and ((ii, jj) not in seen or k - 1 > seen[ii, jj]):
							seen[ii, jj] = k - 1
							q2.append((ii, jj, k - 1, c + 1))
			q = q2
		return -1

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		K = k
		(q1, q2) = ({}, {})
		q1[0, 0] = 0
		q2[m - 1, n - 1] = 0
		level = 0
		(seen1, seen2) = ({}, {})
		seen1[0, 0] = 0
		seen2[m - 1, n - 1] = 0
		while q1 and q2:
			tmp = {}
			if len(q2) < len(q1):
				(q1, q2) = (q2, q1)
				(seen1, seen2) = (seen2, seen1)
			for ((i, j), k) in q1.items():
				if (i, j) in q2 and k + q2[i, j] <= K:
					return level
				for (ii, jj) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
					if 0 <= ii < m and 0 <= jj < n:
						if grid[ii][jj] == 0 and ((ii, jj) not in seen1 or k < seen1[ii, jj]):
							seen1[ii, jj] = k
							tmp[ii, jj] = k
						if grid[ii][jj] == 1 and k < K and ((ii, jj) not in seen1 or k + 1 < seen1[ii, jj]):
							seen1[ii, jj] = k + 1
							tmp[ii, jj] = k + 1
			q1 = tmp
			level += 1
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		q = collections.deque([(0, 0, k)])
		(m, n) = (len(grid), len(grid[0]))
		step = 0
		visited = set()
		while q:
			nq = collections.deque()
			while q:
				(x, y, curk) = q.popleft()
				visited.add((x, y, curk))
				if x == m - 1 and y == n - 1:
					return step
				for (dx, dy) in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
					nx = x + dx
					ny = y + dy
					if not (0 <= nx < m and 0 <= ny < n):
						continue
					if grid[nx][ny] == 1 and curk - 1 >= 0 and ((nx, ny, curk - 1) not in visited):
						nq.append((nx, ny, curk - 1))
						visited.add((nx, ny, curk - 1))
					elif grid[nx][ny] == 0 and (nx, ny, curk) not in visited:
						nq.append((nx, ny, curk))
						visited.add((nx, ny, curk))
			step += 1
			q = nq
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		queue = collections.deque([(0, 0, k, 0)])
		h = len(grid)
		if h == 0:
			return 0
		w = len(grid[0])
		visited = set()
		while len(queue) > 0:
			(i, j, k_left, step) = queue.popleft()
			if i < 0 or j < 0 or i >= h or (j >= w):
				continue
			if grid[i][j] == 1:
				k_left -= 1
			if k_left < 0 or (i, j, k_left) in visited:
				continue
			visited.add((i, j, k_left))
			if i == h - 1 and j == w - 1:
				return step
			queue.append((i + 1, j, k_left, step + 1))
			queue.append((i - 1, j, k_left, step + 1))
			queue.append((i, j + 1, k_left, step + 1))
			queue.append((i, j - 1, k_left, step + 1))
		return -1


from collections import deque
from typing import List

class Solution:

	def getNeighbors(self, width, height, node):
		(row, column) = node
		for (dr, dc) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
			(rr, cc) = (row + dr, column + dc)
			if 0 <= rr < height and 0 <= cc < width:
				yield (rr, cc)

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(height, width) = (len(grid), len(grid[0]))
		queue = deque()
		queue.append(((0, 0), k))
		(result, visited) = (0, set())
		visited.add(((0, 0), k))
		while queue:
			length = len(queue)
			for _ in range(length):
				(node, remove_capacity) = queue.popleft()
				if node == (height - 1, width - 1):
					return result
				for (rr, cc) in self.getNeighbors(width, height, node):
					capacity = remove_capacity - grid[rr][cc]
					key = ((rr, cc), capacity)
					if key not in visited and capacity >= 0:
						queue.append(key)
						visited.add(key)
			result += 1
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		innerQueue = deque()
		innerQueue.append((0, 0, 0, 0))
		gridSet = set()
		gridSet.add((0, 0, 0))
		directions = [[-1, 0], [0, -1], [1, 0], [0, 1]]
		ans = -1
		while len(innerQueue) > 0:
			(i, j, obstacle, distance) = innerQueue.popleft()
			if i == len(grid) - 1 and j == len(grid[0]) - 1:
				ans = distance
				return ans
			for direction in directions:
				ni = i + direction[0]
				nj = j + direction[1]
				if ni >= 0 and nj >= 0 and (ni < len(grid)) and (nj < len(grid[0])):
					if grid[ni][nj] == 1 and (ni, nj, obstacle + 1) not in gridSet and (obstacle + 1 <= k):
						gridSet.add((ni, nj, obstacle + 1))
						innerQueue.append((ni, nj, obstacle + 1, distance + 1))
					elif grid[ni][nj] == 0 and (ni, nj, obstacle) not in gridSet:
						gridSet.add((ni, nj, obstacle))
						innerQueue.append((ni, nj, obstacle, distance + 1))
		return ans


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if len(grid) == 1 and len(grid[0]) == 1:
			return 0
		q = collections.deque()
		visited = set((0, 0, 0))
		q.append(((0, 0), 0))
		level = 1
		while len(q) > 0:
			length = len(q)
			for i in range(length):
				curr = q.popleft()
				for (dx, dy) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
					new_x = curr[0][0] + dx
					new_y = curr[0][1] + dy
					if new_x >= 0 and new_x < len(grid) and (new_y >= 0) and (new_y < len(grid[0])):
						obs = curr[1]
						if grid[new_x][new_y] == 1:
							obs += 1
						if (new_x, new_y, obs) not in visited and obs <= k:
							visited.add((new_x, new_y, obs))
							q.append(((new_x, new_y), obs))
							if new_x == len(grid) - 1 and new_y == len(grid[0]) - 1:
								return level
			level += 1
		return -1


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if not grid or not grid[0]:
			return -1

		def boundary_check(r, c):
			return 0 <= r < len(grid) and 0 <= c < len(grid[0])
		q = deque([((0, 0, k), 0)])
		visited = set((0, 0, k))
		directions = ((0, 1), (0, -1), (1, 0), (-1, 0))
		end_cell = (len(grid) - 1, len(grid[0]) - 1)
		while q:
			((r, c, obst_rem), jumps) = q.popleft()
			if (r, c) == end_cell:
				return jumps
			for (x, y) in directions:
				(nxt_r, nxt_c) = (r + x, c + y)
				if boundary_check(nxt_r, nxt_c):
					if grid[nxt_r][nxt_c] == 0:
						nxt_state = (nxt_r, nxt_c, obst_rem)
					elif obst_rem > 0:
						nxt_state = (nxt_r, nxt_c, obst_rem - 1)
					else:
						continue
					if nxt_state not in visited:
						visited.add(nxt_state)
						q.append((nxt_state, jumps + 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(q, d) = (deque([(0, 0)]), {(0, 0): (0, 0)})
		while q:
			(i, j) = q.popleft()
			(dist, obst) = d[i, j]
			for (m, n) in [(i - 1, j), (i, j - 1), (i + 1, j), (i, j + 1)]:
				if 0 <= m < len(grid) and 0 <= n < len(grid[0]):
					if obst + grid[m][n] < d.get((m, n), (0, float('inf')))[1]:
						d[m, n] = (dist + 1, obst + grid[m][n])
						q.append((m, n))
			(dist, obst) = d.get((len(grid) - 1, len(grid[0]) - 1), (0, float('inf')))
			if obst <= k:
				return dist
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		dp = [[[float('inf')] * (k + 1) for _ in range(n)] for _ in range(m)]
		dp[0][0][k] = 0
		q = deque([(0, 0, k)])

		def move(i, j, k):
			for (di, dj) in ((-1, 0), (1, 0), (0, -1), (0, 1)):
				(ni, nj) = (i + di, j + dj)
				if 0 <= ni < m and 0 <= nj < n and (k >= grid[ni][nj]):
					yield (ni, nj, k - grid[ni][nj])
		while q:
			(i, j, k) = q.pop()
			if i == m - 1 and j == n - 1:
				return dp[i][j][k]
			for (ni, nj, nk) in move(i, j, k):
				if dp[i][j][k] + 1 < dp[ni][nj][nk]:
					dp[ni][nj][nk] = dp[i][j][k] + 1
					q.appendleft((ni, nj, nk))
		return -1


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		m = len(grid)
		n = len(grid[0])
		if m == 1 and n == 1:
			return 0
		parent = {}
		start = (0, 0, k)
		goal = (m - 1, n - 1)
		parent[start] = None
		k_left = -1
		frontier = deque([start])
		while len(frontier) > 0:
			(x, y, z) = frontier.popleft()
			if (goal[0], goal[1], k_left) in parent:
				break
			for (i, j) in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
				if min(i, j) < 0 or i >= m or j >= n:
					continue
				if grid[i][j] == 0 and (i, j, z) not in parent:
					parent[i, j, z] = (x, y, z)
					frontier.append((i, j, z))
					if (i, j) == goal:
						k_left = z
						break
				elif grid[i][j] == 1 and z > 0 and ((i, j, z - 1) not in parent):
					parent[i, j, z - 1] = (x, y, z)
					frontier.append((i, j, z - 1))
					if (i, j) == goal:
						k_left = z - 1
						break
		current = (goal[0], goal[1], k_left)
		steps = 0
		if current not in parent:
			return -1
		while parent[current] is not None:
			steps += 1
			current = parent[current]
		return steps


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		visited = set()

		def bfs(steps, x, y, oc):
			visited.add((x, y, oc))
			q = collections.deque()
			q.append((steps, x, y, oc))
			while q:
				(steps, r, c, obstacleCount) = q.popleft()
				if r == m - 1 and c == n - 1:
					return steps
				for (i, j, oc) in getneighbors(r, c, obstacleCount):
					if (i, j, oc) not in visited:
						visited.add((i, j, oc))
						q.append((steps + 1, i, j, oc))
			return -1

		def getneighbors(x, y, oc):
			result = []
			for (x, y) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
				if 0 <= x < m and 0 <= y < n:
					newoc = oc + grid[x][y]
					if grid[x][y] == 0 or (grid[x][y] == 1 and newoc <= k):
						yield (x, y, newoc)
			return result
		return bfs(0, 0, 0, 0)


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if len(grid) == 0:
			return 0
		m = len(grid)
		n = len(grid[0])
		visited = set()
		directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
		visited.add((0, 0, 0))
		queue = [(0, 0, 0, 0)]
		while queue:
			(lvl, out, x, y) = queue.pop(0)
			if x == m - 1 and y == n - 1:
				return lvl
			for (dx, dy) in directions:
				if x + dx < 0 or y + dy < 0 or x + dx >= m or (y + dy >= n):
					continue
				if grid[x + dx][y + dy] == 0 and (out, x + dx, y + dy) not in visited:
					visited.add((out, x + dx, y + dy))
					queue.append((lvl + 1, out, x + dx, y + dy))
				if grid[x + dx][y + dy] == 1 and out < k and ((out + 1, x + dx, y + dy) not in visited):
					visited.add((out + 1, x + dx, y + dy))
					queue.append((lvl + 1, out + 1, x + dx, y + dy))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		m = len(grid)
		n = len(grid[0])
		queue = collections.deque()
		queue.append((0, 0, 0, k))
		dirs = ((-1, 0), (1, 0), (0, -1), (0, 1))
		visited = set()
		while queue:
			(x, y, level, k) = queue.popleft()
			if x == m - 1 and y == n - 1:
				return level
			if (x, y, k) in visited:
				continue
			visited.add((x, y, k))
			for (dx, dy) in dirs:
				xx = x + dx
				yy = y + dy
				if xx < 0 or xx >= m or yy < 0 or (yy >= n):
					continue
				if grid[xx][yy] == 0:
					queue.append((xx, yy, level + 1, k))
				elif k > 0:
					queue.append((xx, yy, level + 1, k - 1))
		return -1


import collections

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		stack = collections.deque([(0, 0, 0, k)])
		visited = set()
		m = len(grid) - 1
		n = len(grid[0]) - 1
		while stack:
			(curr_x, curr_y, steps, remaining) = stack.popleft()
			if curr_x == m and curr_y == n:
				return steps
			if (curr_x, curr_y, remaining) in visited:
				continue
			visited.add((curr_x, curr_y, remaining))
			directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
			for (i, j) in directions:
				next_x = curr_x + i
				next_y = curr_y + j
				if next_x >= 0 and next_y >= 0 and (next_x <= m) and (next_y <= n):
					if grid[next_x][next_y] == 0 and (next_x, next_y, remaining) not in visited:
						stack.append((next_x, next_y, steps + 1, remaining))
					elif remaining - 1 >= 0 and (next_x, next_y, remaining - 1) not in visited:
						stack.append((next_x, next_y, steps + 1, remaining - 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(q, nq, d) = (set([(0, 0)]), set(), {(0, 0): (0, 0)})
		while q:
			for (i, j) in q:
				(dist, obst) = d[i, j]
				for (m, n) in [(i - 1, j), (i, j - 1), (i + 1, j), (i, j + 1)]:
					if 0 <= m < len(grid) and 0 <= n < len(grid[0]):
						if obst + grid[m][n] < d.get((m, n), (0, float('inf')))[1]:
							d[m, n] = (dist + 1, obst + grid[m][n])
							nq.add((m, n))
				(dist, obst) = d.get((len(grid) - 1, len(grid[0]) - 1), (0, float('inf')))
				if obst <= k:
					return dist
			(q, nq) = (nq, set())
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		m = len(grid)
		n = len(grid[0])
		visited = [[[False for _ in range(k + 1)] for _ in range(n)] for _ in range(m)]
		initialK = k - grid[0][0] - grid[m - 1][n - 1]
		if initialK < 0:
			return -1
		visited[0][0][initialK] = True
		initial = ((0, 0), initialK)
		queue = [initial]
		length = 0
		while queue:
			size = len(queue)
			length += 1
			for _ in range(size):
				(node, kLeft) = queue.pop(0)
				(x, y) = node
				if kLeft >= 0 and x == m - 1 and (y == n - 1):
					return length - 1
				for direction in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
					nextX = x + direction[0]
					nextY = y + direction[1]
					if 0 <= nextX < m and 0 <= nextY < n:
						nextKLeft = kLeft - grid[nextX][nextY]
						if nextKLeft < 0 or visited[nextX][nextY][nextKLeft]:
							continue
						else:
							if nextX == m - 1 and nextY == n - 1:
								return length
							queue.append(((nextX, nextY), nextKLeft))
							visited[nextX][nextY][nextKLeft] = True
		return -1


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
		q = deque([(0, 0, 0, k)])
		visited = set([(0, 0, k)])
		cur_min = -1
		while q:
			(row, col, dist, cur_k) = q.popleft()
			if row == len(grid) - 1 and col == len(grid[0]) - 1:
				if cur_min == -1:
					cur_min = dist
				else:
					cur_min = min(cur_min, dist)
			if cur_min != -1 and dist >= cur_min:
				continue
			for (i, j) in directions:
				if row + i < len(grid) and row + i >= 0 and (col + j < len(grid[0])) and (col + j >= 0):
					if (row + i, col + j, cur_k) not in visited and grid[row + i][col + j] == 0:
						q.append((row + i, col + j, dist + 1, cur_k))
						visited.add((row + i, col + j, cur_k))
					if (row + i, col + j, cur_k - 1) not in visited and grid[row + i][col + j] == 1:
						if cur_k > 0:
							q.append((row + i, col + j, dist + 1, cur_k - 1))
							visited.add((row + i, col + j, cur_k - 1))
		return cur_min


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		queue = deque()
		visited = set()
		queue.append((0, 0, k, 0))
		while queue:
			(i, j, r, l) = queue.popleft()
			if (i, j, r) in visited:
				continue
			visited.add((i, j, r))
			if grid[i][j] == 1:
				r -= 1
			if r < 0:
				continue
			if i == len(grid) - 1 and j == len(grid[0]) - 1:
				return l
			neighbors = {(1, 0), (0, 1), (-1, 0), (0, -1)}
			for n in neighbors:
				(x, y) = (i + n[0], j + n[1])
				if 0 <= x < len(grid) and 0 <= y < len(grid[0]):
					queue.append((x, y, r, l + 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		q = []
		n = len(grid)
		m = len(grid[0])
		v = {}
		q.append([0, 0, 0, k])
		while q:
			(i, j, d, r) = q.pop(0)
			if i == n - 1 and j == m - 1:
				return d
			let = [[i + 1, j], [i, j + 1], [i - 1, j], [i, j - 1]]
			for (x, y) in let:
				if 0 <= x < n and 0 <= y < m:
					if grid[x][y] == 0 and (x, y, r) not in v:
						v[x, y, r] = 1
						q.append([x, y, d + 1, r])
					elif r > 0 and (x, y, r) not in v:
						v[x, y, r] = 1
						q.append([x, y, d + 1, r - 1])
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(n, m) = (len(grid), len(grid[0]))
		vis = set()
		vis.add((0, 0, 0))
		q = [(0, 0, 0, 0)]

		def neighbors(i, j, oc):
			for (x, y) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
				if 0 <= x < n and 0 <= y < m:
					newoc = oc + grid[x][y]
					if newoc <= k and (x, y, newoc) not in vis:
						yield (x, y, newoc)
		while q:
			(steps, i, j, obstacleCount) = q.pop(0)
			if i == n - 1 and j == m - 1:
				return steps
			else:
				for (x, y, oc) in neighbors(i, j, obstacleCount):
					vis.add((x, y, oc))
					q.append((steps + 1, x, y, oc))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if grid[0][0] == 1 and k == 0:
			return -1
		(m, n) = (len(grid), len(grid[0]))
		a = k if grid[0][0] == 0 else k - 1
		q = collections.deque([(0, 0, 0, a, [(0, 0)])])
		visited = set()
		visited.add((0, 0))
		while q:
			(i, j, step, available, path) = q.popleft()
			if i == m - 1 and j == n - 1:
				return step
			for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:
				if 0 <= ni < m and 0 <= nj < n:
					if grid[ni][nj] == 1 and (not available):
						continue
					if (ni, nj, available) not in visited:
						visited.add((ni, nj, available))
						if grid[ni][nj] == 0:
							q.append([ni, nj, step + 1, available, path + [(ni, nj)]])
						if grid[ni][nj] == 1:
							if available:
								q.append([ni, nj, step + 1, available - 1, path + [(ni, nj)]])
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		if m == n == 1:
			return 0
		queue = [(0, 0, k)]
		visited = set((0, 0))
		steps = 0
		while queue:
			new_queue = []
			for (x, y, obs) in queue:
				for (i, j) in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
					if 0 <= i < m and 0 <= j < n:
						if grid[i][j] == 1 and obs > 0 and ((i, j, obs - 1) not in visited):
							new_queue.append((i, j, obs - 1))
							visited.add((i, j, obs - 1))
						if grid[i][j] == 0 and (i, j, obs) not in visited:
							if i == m - 1 and j == n - 1:
								return steps + 1
							visited.add((i, j, obs))
							new_queue.append((i, j, obs))
			if new_queue:
				queue = new_queue
				steps += 1
			else:
				break
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if len(grid) == 1 and len(grid[0]) == 1:
			return 0
		directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
		queue = deque()
		queue.append((0, 0, k, 0))
		visited = set((0, 0, k))
		count = 0
		while queue:
			(x, y, obstacles, steps) = queue.popleft()
			visited.add((x, y, obstacles))
			for (dx, dy) in directions:
				if 0 <= x + dx < len(grid) and 0 <= y + dy < len(grid[0]):
					if grid[x + dx][y + dy] == 0 and (x + dx, y + dy, obstacles) not in visited:
						if x + dx == len(grid) - 1 and y + dy == len(grid[0]) - 1:
							return steps + 1
						queue.append((x + dx, y + dy, obstacles, steps + 1))
						visited.add((x + dx, y + dy, obstacles))
					if grid[x + dx][y + dy] == 1 and obstacles > 0 and ((x + dx, y + dy, obstacles - 1) not in visited):
						queue.append((x + dx, y + dy, obstacles - 1, steps + 1))
						visited.add((x + dx, y + dy, obstacles - 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if len(grid) == 0 or len(grid[0]) == 0:
			return -1
		if grid[0][0] == 1:
			queue = [(0, 0, 1, 0)]
			visited = set([(0, 0, 1)])
		else:
			queue = [(0, 0, 0, 0)]
			visited = set([(0, 0, 0)])
		direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
		while queue != []:
			current = queue.pop(0)
			if current[0] == len(grid) - 1 and current[1] == len(grid[0]) - 1:
				return current[3]
			for d in direction:
				n = (current[0] + d[0], current[1] + d[1])
				if 0 <= n[0] < len(grid) and 0 <= n[1] < len(grid[0]):
					blocks = current[2]
					if grid[n[0]][n[1]] == 1:
						blocks += 1
					if blocks <= k and (n[0], n[1], blocks) not in visited:
						queue.append((n[0], n[1], blocks, current[3] + 1))
						visited.add((n[0], n[1], blocks))
		return -1


class Solution:

	def shortestPath(self, grid, k):
		m = len(grid)
		n = len(grid[0])
		q = [(0, 0, 0, 0)]
		dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		visited = set((0, 0, 0))
		i = j = obs = 0
		while q:
			(x, y, obs, steps) = q.pop(0)
			if x == m - 1 and y == n - 1:
				return steps
			for (dx, dy) in dirs:
				i = x + dx
				j = y + dy
				if 0 <= i < m and 0 <= j < n:
					newObs = obs + grid[i][j]
					if newObs <= k and (i, j, newObs) not in visited:
						q.append((i, j, newObs, steps + 1))
						visited.add((i, j, newObs))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:

		def move(pos_x, pos_y, obs, steps):
			if pos_x < 0 or pos_x >= len(grid) or pos_y < 0 or (pos_y >= len(grid[0])):
				return
			if grid[pos_x][pos_y] == 1:
				if obs == 0:
					return
				obs -= 1
			if self.memo.get((pos_x, pos_y, obs), 2000) <= steps:
				return
			self.memo.update({(pos_x, pos_y, obs): steps})
			q.append((pos_x, pos_y, obs, steps))
			if pos_x == len(grid) - 1 and pos_y == len(grid[0]) - 1:
				self.ans = steps
		self.ans = None
		q = deque([(0, 0, k, 0)])
		self.memo = {(0, 0, k): 0}
		while q:
			(pos_x, pos_y, obs, steps) = q.popleft()
			if pos_x == len(grid) - 1 and pos_y == len(grid[0]) - 1:
				return steps
			move(pos_x - 1, pos_y, obs, steps + 1)
			move(pos_x + 1, pos_y, obs, steps + 1)
			move(pos_x, pos_y - 1, obs, steps + 1)
			move(pos_x, pos_y + 1, obs, steps + 1)
			if self.ans is not None:
				return self.ans
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if not grid or not grid[0]:
			return 0
		n = len(grid)
		m = len(grid[0])
		hp = []
		heapq.heappush(hp, (0, 0, 0, 0))
		visited = set()
		visited.add((0, 0, 0))
		while hp:
			(step, d, i, j) = heapq.heappop(hp)
			if i == n - 1 and j == m - 1:
				return step
			for (x, y) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
				if x < 0 or x >= n or y < 0 or (y >= m) or ((x, y, d + grid[x][y]) in visited) or (grid[x][y] + d > k):
					continue
				visited.add((x, y, grid[x][y] + d))
				heapq.heappush(hp, (step + 1, d + grid[x][y], x, y))
		return -1


import heapq

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		(q, seen) = ([(m - 1 + n - 1 + 0, 0, 0, 0, 0)], set())
		while q:
			(_, d, x, y, z) = heapq.heappop(q)
			if (x, y) == (m - 1, n - 1):
				return d
			if (x, y, z) not in seen:
				seen.add((x, y, z))
				for (dx, dy) in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
					(i, j) = (x + dx, y + dy)
					if 0 <= i < m and 0 <= j < n:
						if grid[i][j] == 0:
							heapq.heappush(q, (m - 1 - i + n - 1 - j + d + 1, d + 1, i, j, z))
						elif z + 1 <= k:
							heapq.heappush(q, (m - 1 - i + n - 1 - j + d + 1, d + 1, i, j, z + 1))
		return -1


from collections import deque
import numpy as np

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		m = len(grid)
		n = len(grid[0])
		dq = deque()
		cache = {}
		minStep = np.inf
		s = (0, 0, 0, 0)
		cache[s[:3]] = s[-1]
		dq.append(s)
		while dq:
			(i, j, ob, step) = dq.popleft()
			if i == m - 1 and j == n - 1:
				minStep = min(minStep, step)
				continue
			for (x, y) in [(i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j)]:
				if x >= 0 and x < m and (y >= 0) and (y < n):
					if ob + grid[x][y] > k or step + 1 > minStep:
						continue
					if (x, y, ob + grid[x][y]) not in cache or step + 1 < cache[x, y, ob + grid[x][y]]:
						dq.append((x, y, ob + grid[x][y], step + 1))
						cache[x, y, ob + grid[x][y]] = step + 1
		return -1 if minStep == np.inf else minStep


class Solution:
	dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if not grid or not grid[0]:
			return -1
		(n, m) = (len(grid), len(grid[0]))
		queue = deque()
		queue.append((0, 0, k))
		visited = set()
		visited.add((0, 0, k))
		step = 0
		while queue:
			size = len(queue)
			for _ in range(size):
				(i, j, chances) = queue.popleft()
				if i == n - 1 and j == m - 1:
					return step
				for d in Solution.dirs:
					(x, y) = (i + d[0], j + d[1])
					if x < 0 or x >= n or y < 0 or (y >= m):
						continue
					if grid[x][y] == 0:
						if (x, y, chances) not in visited:
							queue.append((x, y, chances))
							visited.add((x, y, chances))
					elif grid[x][y] == 1:
						if chances == 0:
							continue
						if (x, y, chances - 1) not in visited:
							queue.append((x, y, chances - 1))
							visited.add((x, y, chances - 1))
			step += 1
		return -1


from typing import *
from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		m = len(grid)
		n = len(grid[0])
		dis = [[[float('inf') for _ in range(k + 1)] for _ in range(n)] for _ in range(m)]
		dis[0][0][0] = 0
		vis = [[[False for _ in range(k + 1)] for _ in range(n)] for _ in range(m)]
		q = deque([(0, 0, k, 0)])
		vis[0][0][k] = True
		while q:
			(x, y, remain_chance, d) = q.popleft()
			if x == m - 1 and y == n - 1:
				return d
			dis[x][y][k] = d
			for (x1, y1) in [(x, y - 1), (x, y + 1), (x + 1, y), (x - 1, y)]:
				if x1 < 0 or x1 >= m or y1 < 0 or (y1 >= n):
					continue
				if grid[x1][y1] == 1:
					if remain_chance == 0:
						continue
					if vis[x1][y1][remain_chance - 1]:
						continue
					q.append((x1, y1, remain_chance - 1, d + 1))
					vis[x1][y1][remain_chance - 1] = True
				else:
					if vis[x1][y1][remain_chance]:
						continue
					q.append((x1, y1, remain_chance, d + 1))
					vis[x1][y1][remain_chance] = True
		return -1


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		queue = deque([(0, 0, 0)])
		seen = set([(0, 0, 0)])
		nsteps = -1
		while queue:
			levelSize = len(queue)
			nsteps += 1
			for _ in range(levelSize):
				(i, j, t) = queue.popleft()
				if i == m - 1 and j == n - 1:
					return nsteps
				for (x, y) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
					if 0 <= x < m and 0 <= y < n:
						is_obs = grid[x][y] == 1
						q = t + int(is_obs)
						if q <= k and (x, y, q) not in seen:
							queue.append((x, y, q))
							seen.add((x, y, q))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if not grid:
			return -1
		(m, n) = (len(grid), len(grid[0]))
		if grid[0][0] != 0:
			return -1
		if m == 1 and n == 1:
			return 0
		di = [(-1, 0), (1, 0), (0, -1), (0, 1)]

		def get_nei(i, j):
			return [(i + x, j + y) for (x, y) in di if 0 <= i + x <= m - 1 and 0 <= j + y <= n - 1]
		seen = set([(0, 0, k)])
		q = collections.deque()
		q.append((0, 0, k, 0))
		while q:
			(i, j, ob, depth) = q.popleft()
			for (x, y) in get_nei(i, j):
				cob = ob
				if x == m - 1 and y == n - 1 and (cob >= 0):
					return depth + 1
				if grid[x][y] == 1 and cob > 0 and ((x, y, cob - 1) not in seen):
					seen.add((x, y, cob - 1))
					q.append((x, y, cob - 1, depth + 1))
				if grid[x][y] == 0 and cob >= 0 and ((x, y, cob) not in seen):
					seen.add((x, y, cob))
					q.append((x, y, cob, depth + 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(EMPTY, OBSTACLE) = (0, 1)
		(m, n) = (len(grid), len(grid[0]))
		distance = defaultdict(lambda : math.inf)
		distance[0, 0, 0] = 0
		pq = [(0, 0, 0, 0)]
		while pq:
			(d, e, i, j) = heapq.heappop(pq)
			if distance[e, i, j] < d:
				continue
			if i == m - 1 and j == n - 1:
				return d
			for (ni, nj) in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
				if 0 <= ni < m and 0 <= nj < n:
					ne = e + int(grid[ni][nj] == OBSTACLE)
					if ne <= k:
						nd = d + 1
						if nd < distance[ne, ni, nj]:
							distance[ne, ni, nj] = nd
							heapq.heappush(pq, (nd, ne, ni, nj))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(rows, cols) = (len(grid), len(grid[0]))
		if rows == 1 and cols == 1:
			return 0
		visited = set((0, 0, k))
		q = deque([(0, 0, k, 0)])
		while q:
			(r, c, k_rem, d) = q.popleft()
			edges = [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]
			edges = [(x, y) for (x, y) in edges if x >= 0 and x < rows and (y >= 0) and (y < cols)]
			edges = [(x, y, k_rem - 1 if grid[x][y] == 1 else k_rem) for (x, y) in edges]
			edges = [edge for edge in edges if edge[2] >= 0 and edge not in visited]
			for (x, y, rem) in edges:
				if x == rows - 1 and y == cols - 1:
					return d + 1
				q.append((x, y, rem, d + 1))
				visited.add((x, y, rem))
		return -1


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if not grid:
			return 0
		if len(grid) == 1 and len(grid[0]) == 1:
			return 0
		(m, n) = (len(grid), len(grid[0]))
		queue = deque([(0, 0, 0, k)])
		visited = set()
		visited.add((0, 0, k))
		direction = [[1, 0], [0, 1], [0, -1], [-1, 0]]
		while queue:
			(cur_x, cur_y, cur_count, cur_k) = queue.popleft()
			for (i, j) in direction:
				next_x = cur_x + i
				next_y = cur_y + j
				if 0 <= next_x < m and 0 <= next_y < n:
					if grid[next_x][next_y] == 1 and cur_k > 0 and ((next_x, next_y, cur_k - 1) not in visited):
						visited.add((next_x, next_y, cur_k - 1))
						queue.append((next_x, next_y, cur_count + 1, cur_k - 1))
					if grid[next_x][next_y] == 0 and (next_x, next_y, cur_k) not in visited:
						if next_x == m - 1 and next_y == n - 1:
							return cur_count + 1
						visited.add((next_x, next_y, cur_k))
						queue.append((next_x, next_y, cur_count + 1, cur_k))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(row, col) = (len(grid), len(grid[0]))
		q = collections.deque()
		q.append((0, 0, 0, k))
		visit = set()
		while q:
			(x, y, dist, k) = q.popleft()
			if x == row - 1 and y == col - 1:
				return dist
			if (x, y, k) in visit:
				continue
			visit.add((x, y, k))
			dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
			for (i, j) in dirs:
				if 0 <= x + i < row and 0 <= y + j < col:
					if grid[x + i][y + j] == 0:
						q.append((x + i, y + j, dist + 1, k))
					elif grid[x + i][y + j] == 1 and k > 0:
						q.append((x + i, y + j, dist + 1, k - 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		cache = {}
		m = len(grid)
		n = len(grid[0])
		if m == 1 and n == 1:
			if grid[0][0] == 0:
				return 0
			if grid[0][0] == 1:
				if k >= 1:
					return 0
				return -1

		def get_nexts(i, j, k):
			nxts = [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]
			nxts = [(x, y) for (x, y) in nxts if x >= 0 and x < m and (y >= 0) and (y < n) and ((x, y) not in pathnodes)]
			nxts_steps = []
			for (x, y) in nxts:
				if grid[x][y] == 0:
					nxts_steps.append((x, y, k))
				if grid[x][y] and k >= 1:
					nxts_steps.append((x, y, k - 1))
			return nxts_steps
		pathnodes = set()
		roots = [(0, 0, k)]
		d = 0
		includes = set(roots)
		while roots:
			next_level = []
			for root in roots:
				nxts = get_nexts(*root)
				for nxt in nxts:
					if nxt in includes:
						continue
					if nxt[:2] == (m - 1, n - 1):
						return d + 1
					next_level.append(nxt)
					includes.add(nxt)
			roots = next_level
			d += 1
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(n, m) = (len(grid), len(grid[0]))
		if n == 1 and m == 1:
			return 0
		dist = {(0, 0, k): 0}
		queue = deque([(0, 0, k)])
		while queue:
			(i, j, p) = queue.popleft()
			for (r, s) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
				if r == n - 1 and s == m - 1:
					return dist[i, j, p] + 1
				if 0 <= r < n and 0 <= s < m:
					if grid[r][s] == 0 and (r, s, p) not in dist:
						dist[r, s, p] = dist[i, j, p] + 1
						queue.append((r, s, p))
					elif p > 0 and (r, s, p - 1) not in dist:
						dist[r, s, p - 1] = dist[i, j, p] + 1
						queue.append((r, s, p - 1))
		return -1


from collections import deque

class Solution:

	def shortestPath(self, g: List[List[int]], k: int) -> int:
		(m, n) = (len(g), len(g[0]))
		q = collections.deque([(0, 0, k, 0)])
		seen = {(0, 0, k)}
		while q:
			(x, y, r, s) = q.popleft()
			if x == m - 1 and y == n - 1:
				return s
			for (i, j) in ((0, 1), (1, 0), (-1, 0), (0, -1)):
				if 0 <= x + i < m and 0 <= y + j < n:
					nr = r - (g[x + i][y + j] == 1)
					if (x + i, y + j, nr) not in seen and nr >= 0:
						q.append((x + i, y + j, nr, s + 1))
						seen.add((x + i, y + j, nr))
		return -1


class Solution:

	def shortestPath(self, map: List[List[int]], k: int) -> int:
		import collections
		(h, w) = (len(map), len(map[0]))

		def check_map(i, j, rw):
			if i >= h or i < 0:
				return 1
			if j >= w or j < 0:
				return 1
			if map[i][j] == 1 and rw > 0:
				return -1
			if map[i][j] == 1 and rw == 0:
				return 1
			return 0
		start_pos = (0, 0, 0, k)
		q = collections.deque([])
		q.append(start_pos)
		seen = set()
		seen.add((0, 0, k))
		while q:
			(i, j, step, rw) = q.popleft()
			if i == h - 1 and j == w - 1:
				return step
			fw = [i - 1, j]
			bw = [i + 1, j]
			lf = [i, j - 1]
			rt = [i, j + 1]
			moves = [bw, rt, lf, fw]
			for move in moves:
				(ni, nj) = move
				map_state = check_map(ni, nj, rw)
				if map_state in (0, -1) and (ni, nj, rw + map_state) not in seen:
					q.append([ni, nj, step + 1, rw + map_state])
					seen.add((ni, nj, rw + map_state))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		q = collections.deque()
		if grid[0][0] == 1:
			k -= 1
		q.append([0, k, 0, 0])
		(m, n) = (len(grid), len(grid[0]))
		record = set()
		record.add((0, 0, k))
		while q:
			l = len(q)
			for _ in range(l):
				(step, s, x, y) = q.popleft()
				if x == m - 1 and y == n - 1:
					if grid[x][y] == 1 and s == 0:
						continue
					return step
				for (i, j) in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
					if 0 <= i < m and 0 <= j < n:
						if grid[i][j] == 1:
							if s >= 1 and (i, j, s - 1) not in record:
								record.add((i, j, s - 1))
								q.append([step + 1, s - 1, i, j])
						elif (i, j, s) not in record:
							record.add((i, j, s))
							q.append([step + 1, s, i, j])
		return -1


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if len(grid) == 1 and len(grid[0]) == 1:
			return 0
		queue = deque([(0, 0, k, 0)])
		visited = set((0, 0, k))
		directions = [(0, 1), (1, 0), (-1, 0), (0, -1)]
		while queue:
			(row, col, elim, steps) = queue.popleft()
			for (r, c) in directions:
				new_row = row + r
				new_col = col + c
				if new_row < 0 or new_row >= len(grid) or new_col < 0 or (new_col >= len(grid[0])):
					continue
				if grid[new_row][new_col] == 1 and elim > 0 and ((new_row, new_col, elim - 1) not in visited):
					queue.append((new_row, new_col, elim - 1, steps + 1))
					visited.add((new_row, new_col, elim - 1))
				if grid[new_row][new_col] == 0 and (new_row, new_col, elim) not in visited:
					if new_row == len(grid) - 1 and new_col == len(grid[0]) - 1:
						return steps + 1
					queue.append((new_row, new_col, elim, steps + 1))
					visited.add((new_row, new_col, elim))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		frontier = collections.deque([(0, 0, k, 0)])
		seen = {(0, 0, k)}
		while frontier:
			(i, j, d, steps) = frontier.popleft()
			if i == m - 1 and j == n - 1:
				return steps
			for (a, b) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
				(r, c) = (i + a, j + b)
				if 0 <= r < m and 0 <= c < n and ((r, c, d - grid[r][c]) not in seen) and (d >= grid[r][c]):
					seen.add((r, c, d - grid[r][c]))
					frontier.append((r, c, d - grid[r][c], steps + 1))
		return -1


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:

		def inBounds(x, y):
			if x < 0:
				return False
			elif y < 0:
				return False
			elif x >= len(grid[0]):
				return False
			elif y >= len(grid):
				return False
			return True
		target = (len(grid[0]) - 1, len(grid) - 1)
		queue = deque([(0, 0, k, 0)])
		visited = set([(0, 0, k)])
		if target == (0, 0):
			return 0
		while queue:
			(x, y, k, dist) = queue.popleft()
			for (dx, dy) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
				if (x + dx, y + dy) == target:
					return dist + 1
				if not inBounds(x + dx, y + dy):
					continue
				if grid[y + dy][x + dx] == 0 and (x + dx, y + dy, k) not in visited:
					visited.add((x + dx, y + dy, k))
					queue.append((x + dx, y + dy, k, dist + 1))
				elif k > 0 and (x + dx, y + dy, k - 1) not in visited:
					visited.add((x + dx, y + dy, k - 1))
					queue.append((x + dx, y + dy, k - 1, dist + 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		seen = set()
		seen.add((0, 0, k))
		q = deque([(0, 0, k, 0)])
		while q:
			(x, y, remaining, moves) = q.popleft()
			if x == len(grid) - 1 and y == len(grid[0]) - 1:
				return moves
			for (new_x, new_y) in [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]:
				if 0 <= new_x < len(grid) and 0 <= new_y < len(grid[0]):
					if grid[new_x][new_y] == 1 and (new_x, new_y, remaining - 1) not in seen and (remaining > 0):
						seen.add((new_x, new_y, remaining - 1))
						q.append((new_x, new_y, remaining - 1, moves + 1))
					elif grid[new_x][new_y] == 0 and (new_x, new_y, remaining) not in seen:
						seen.add((new_x, new_y, remaining))
						q.append((new_x, new_y, remaining, moves + 1))
		return -1


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if not grid:
			return -1
		rows = len(grid)
		cols = len(grid[0])
		visited = {(0, 0, 0)}
		queue = deque()
		queue.append((0, 0, 0))
		steps = 0
		while queue:
			newqueue = deque()
			for (x, y, r) in queue:
				if x == rows - 1 and y == cols - 1:
					return steps
				for (i, j) in [(x, y - 1), (x, y + 1), (x + 1, y), (x - 1, y)]:
					if i >= 0 and i < rows and (j >= 0) and (j < cols):
						if grid[i][j] == 0 and (i, j, r) not in visited:
							newqueue.append((i, j, r))
							visited.add((i, j, r))
						elif grid[i][j] == 1 and r + 1 <= k and ((i, j, r + 1) not in visited):
							newqueue.append((i, j, r + 1))
							visited.add((i, j, r + 1))
			queue = newqueue
			steps += 1
		return -1


from collections import defaultdict, deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:

		def getNei(x, y):
			for (dx, dy) in dirs:
				(xn, yn) = (x + dx, y + dy)
				if 0 <= xn < m and 0 <= yn < n:
					yield (xn, yn, grid[xn][yn])
		dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]
		(m, n, maxmn) = (len(grid), len(grid[0]), float('inf'))
		costs = [[maxmn] * n for _ in range(m)]
		costs[0][0] = 0
		bfs = collections.deque([(0, 0, 0, k)])
		while bfs:
			(x, y, cost, clears) = bfs.popleft()
			for (xn, yn, blocked) in getNei(x, y):
				newcost = cost + 1
				newclears = clears - blocked
				if newclears >= 0 and newcost < costs[xn][yn]:
					costs[xn][yn] = newcost
					if blocked:
						bfs.append((xn, yn, newcost, newclears))
					else:
						bfs.appendleft((xn, yn, newcost, newclears))
		return -1 if costs[m - 1][n - 1] == maxmn else costs[m - 1][n - 1]


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		q = deque([(0, 0, k, 0)])
		visited = set([(0, 0, k)])

		def move(i, j, k):
			for (di, dj) in ((-1, 0), (1, 0), (0, -1), (0, 1)):
				(ni, nj) = (i + di, j + dj)
				if 0 <= ni < m and 0 <= nj < n:
					nk = k - grid[ni][nj]
					if nk >= 0 and (ni, nj, nk) not in visited:
						yield (ni, nj, nk)
		while q:
			(i, j, k, s) = q.pop()
			if i == m - 1 and j == n - 1:
				return s
			for (ni, nj, nk) in move(i, j, k):
				visited.add((ni, nj, nk))
				q.appendleft((ni, nj, nk, s + 1))
		return -1


class Solution:

	def shortestPath(self, grid, k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		(num_obs, obs) = (0, {})
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					num_obs += 1
		if num_obs <= k:
			return m + n - 2
		q = [(0, 0, 0, k)]
		visited = set()
		while q:
			l = len(q)
			for _ in range(l):
				(step, i, j, rem) = q.pop(0)
				if i == m - 1 and j == n - 1:
					return step
				if (i, j, rem) in visited:
					continue
				visited.add((i, j, rem))
				for (x, y) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
					if 0 <= x < m and 0 <= y < n:
						if grid[x][y] == 0:
							q.append((step + 1, x, y, rem))
						elif grid[x][y] == 1 and rem > 0:
							q.append((step + 1, x, y, rem - 1))
		return -1


import math
import collections
import heapq

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))

		def neighbors(x, y):
			for (dx, dy) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
				if x + dx >= 0 and x + dx < m and (y + dy >= 0) and (y + dy < n):
					yield (x + dx, y + dy)
		bfs = collections.deque([(0, 0, 0, k)])
		visited = set()
		while bfs:
			(i, j, cost, rems) = bfs.popleft()
			if i == m - 1 and j == n - 1:
				return cost
			if (i, j, rems) in visited:
				continue
			visited.add((i, j, rems))
			for (x, y) in neighbors(i, j):
				if grid[x][y] == 1 and rems == 0:
					continue
				if grid[x][y] == 1:
					bfs.append((x, y, cost + 1, rems - 1))
				else:
					bfs.append((x, y, cost + 1, rems))
		return -1


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		queue = deque([(0, 0, k, 0)])
		rows = len(grid)
		cols = len(grid[0])
		ans = float('inf')
		vis = {(0, 0, k): 1}
		while len(queue) > 0:
			(x, y, rem, depth) = queue.popleft()
			if x == rows - 1 and y == cols - 1:
				return depth
			for (i, j) in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
				i += x
				j += y
				if i < 0 or i >= rows or j < 0 or (j >= cols) or ((i, j, rem) in vis) or (grid[i][j] == 1 and rem <= 0):
					continue
				elif grid[i][j] == 0 and (i, j, rem) not in vis:
					vis[i, j, rem] = 1
					queue.append((i, j, rem, depth + 1))
				elif grid[i][j] == 1 and rem > 0 and ((i, j, rem - 1) not in vis):
					vis[i, j, rem - 1] = 1
					queue.append((i, j, rem - 1, depth + 1))
		if ans == float('inf'):
			return -1
		return ans


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		visited = set()
		visited.add((0, 0, k))
		candidates = collections.deque([])
		candidates.append((0, 0, 0, k))
		if len(grid) == 1 and len(grid[0]) == 1:
			return 0
		while len(candidates) > 0:
			(ci, cj, steps, ck) = candidates.popleft()
			if ci == len(grid) - 1 and cj == len(grid[0]) - 1:
				return steps
			for (x, y) in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
				(ni, nj) = (ci + x, cj + y)
				if ni < 0 or nj < 0 or ni >= len(grid) or (nj >= len(grid[0])):
					continue
				if (ni, nj, ck) in visited:
					continue
				if grid[ni][nj] == 1 and ck > 0:
					candidates.append((ni, nj, steps + 1, ck - 1))
					visited.add((ni, nj, ck))
				elif grid[ni][nj] == 0:
					candidates.append((ni, nj, steps + 1, ck))
					visited.add((ni, nj, ck))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		n = len(grid)
		if n == 0:
			return 0
		m = len(grid[0])
		visited = set()
		q = collections.deque([((0, 0), k, 0)])
		while q:
			((r, c), k_left, dist) = q.popleft()
			if ((r, c), k_left) in visited:
				continue
			visited.add(((r, c), k_left))
			if r == n - 1 and c == m - 1:
				return dist
			for (dr, dc) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
				if (0 <= r + dr < n and 0 <= c + dc < m) and (grid[r + dr][c + dc] == 0 or k_left > 0):
					q.append(((r + dr, c + dc), k_left - grid[r + dr][c + dc], dist + 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if grid[0][0] == 1 and k == 0:
			return -1
		(m, n) = (len(grid), len(grid[0]))
		if grid[0][0]:
			k -= 1
		qe = collections.deque([(0, 0, 0, k)])
		visited = set()
		visited.add((0, 0, k))
		dr = [[0, 1], [0, -1], [1, 0], [-1, 0]]
		while qe:
			(i, j, step, k) = qe.popleft()
			if i == m - 1 and j == n - 1:
				return step
			for (x, y) in dr:
				(i1, j1) = (i + x, j + y)
				if i1 < 0 or i1 >= m or j1 < 0 or (j1 >= n):
					continue
				if grid[i1][j1] == 1 and k == 0:
					continue
				if grid[i1][j1] == 1 and k >= 1 and ((i1, j1, k - 1) not in visited):
					visited.add((i1, j1, k - 1))
					qe.append((i1, j1, step + 1, k - 1))
				if grid[i1][j1] == 0 and k >= 0 and ((i1, j1, k) not in visited):
					if i1 == m - 1 and j1 == n - 1:
						return step + 1
					visited.add((i1, j1, k))
					qe.append((i1, j1, step + 1, k))
		return -1


from queue import Queue

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		q = Queue()
		q.put((0, 0, 0, 0))
		visited = {}
		mins = float('inf')
		nr = len(grid)
		nc = len(grid[0])
		while q.qsize() > 0:
			(i, j, obs, count) = q.get()
			if obs > k:
				continue
			if i == nr - 1 and j == nc - 1:
				mins = min(mins, count)
			if (i, j) not in visited or ((i, j) in visited and visited[i, j] > obs):
				visited[i, j] = obs
				for (x, y) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
					if 0 <= x < nr and 0 <= y < nc:
						if grid[x][y] == 1:
							q.put((x, y, obs + 1, count + 1))
						else:
							q.put((x, y, obs, count + 1))
		if mins == float('inf'):
			return -1
		return mins


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		from collections import deque
		(m, n) = (len(grid), len(grid[0]))
		queue = deque()
		queue.append((0, 0, 0, 0))
		directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]
		visited = set([(0, 0, 0)])
		while queue:
			(x, y, elim, path) = queue.popleft()
			if x == m - 1 and y == n - 1:
				return path
			for (dx, dy) in directions:
				(nx, ny) = (x + dx, y + dy)
				if 0 <= nx < m and 0 <= ny < n:
					if grid[nx][ny] == 0 and (nx, ny, elim) not in visited:
						queue.append((nx, ny, elim, path + 1))
						visited.add((nx, ny, elim))
					if grid[nx][ny] == 1 and elim < k and ((nx, ny, elim - 1) not in visited):
						queue.append((nx, ny, elim + 1, path + 1))
						visited.add((nx, ny, elim + 1))
		return -1


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:

		def valid(i, j):
			if i >= 0 and j >= 0 and (i < len(grid)) and (j < len(grid[0])):
				return True
			return False
		dq = deque([(0, 0, k, 0)])
		visited = set()
		res = math.inf

		def search(i, j, k, l):
			if (i, j, k) in visited:
				return False
			visited.add((i, j, k))
			nonlocal res
			if k < 0:
				return False
			if i == len(grid) - 1 and j == len(grid[0]) - 1:
				res = l
				return True
			for (di, dj) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
				if valid(i + di, j + dj):
					next_k = k if grid[i + di][j + dj] == 0 else k - 1
					dq.append((i + di, j + dj, next_k, l + 1))
			return False
		while dq:
			(i, j, k, l) = dq.popleft()
			if search(i, j, k, l):
				break
		return res if res != math.inf else -1


class Solution:

	@staticmethod
	def get_neis(x, y):
		return [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		m = len(grid)
		n = len(grid[0])
		k = min(k, m + n)
		grid_mem = [[[math.inf] * n for _ in range(m)] for ki in range(k + 1)]
		grid_mem[0][0][0] = 0
		visited = {(0, 0)}
		q = collections.deque([(0, 0)])
		while len(q) > 0:
			(i, j) = q.popleft()
			for (x, y) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
				if 0 <= x < m and 0 <= y < n and ((x, y) not in visited) and (grid[x][y] == 0):
					grid_mem[0][x][y] = grid_mem[0][i][j] + 1
					visited.add((x, y))
					q.append((x, y))
		for ki in range(1, k + 1):
			grid_mem[ki][0][0] = 0
			visited = {(0, 0)}
			q = collections.deque([(0, 0)])
			while len(q) > 0:
				(i, j) = q.popleft()
				for (x, y) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
					if 0 <= x < m and 0 <= y < n and ((x, y) not in visited):
						level = ki if grid[x][y] == 0 else ki - 1
						path = math.inf
						for (x2, y2) in self.get_neis(x, y):
							if 0 <= x2 < m and 0 <= y2 < n:
								path = min(path, grid_mem[level][x2][y2])
						grid_mem[ki][x][y] = path + 1
						visited.add((x, y))
						q.append((x, y))
		if grid_mem[-1][-1][-1] < math.inf:
			return grid_mem[-1][-1][-1]
		else:
			return -1


from typing import List

class Solution:

	def __init__(self):
		self.dx = [1, -1, 0, 0]
		self.dy = [0, 0, 1, -1]

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		res = -1
		m = len(grid)
		n = len(grid[0])
		q = [(0, 0, 0, 0)]
		(head, tail) = (0, 1)
		visited = set()
		while head < tail:
			(ci, cj, uk, d) = q[head]
			head += 1
			if ci == m - 1 and cj == n - 1:
				res = d
				break
			else:
				for i in range(0, 4):
					ni = ci + self.dx[i]
					nj = cj + self.dy[i]
					if 0 <= ni < m and 0 <= nj < n:
						if grid[ni][nj] == 1:
							if uk + 1 <= k and (ni, nj, uk + 1) not in visited:
								visited.add((ni, nj, uk + 1))
								q.append((ni, nj, uk + 1, d + 1))
								tail += 1
						elif (ni, nj, uk) not in visited:
							visited.add((ni, nj, uk))
							q.append((ni, nj, uk, d + 1))
							tail += 1
		return res


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:

		def at(point):
			(x, y) = point
			return grid[y][x]

		def valid(point):
			(x, y) = point
			return 0 <= y < len(grid) and 0 <= x < len(grid[y])

		def neighbors(point):
			(x, y) = point
			candidates = [(x, y - 1), (x + 1, y), (x, y + 1), (x - 1, y)]
			for candidate in candidates:
				if valid(candidate):
					yield candidate

		def moves(point, remaining):
			for neighbor in neighbors(point):
				if at(neighbor) == 1 and remaining > 0:
					yield (neighbor, remaining - 1)
				elif at(neighbor) == 0:
					yield (neighbor, remaining)
		start = ((0, 0), k)
		prev = {start: None}

		def path_length(node):
			length = 0
			while node:
				length += 1
				node = prev[node]
			return length
		frontier = deque([start])
		while frontier:
			(point, remaining) = frontier.popleft()
			(x, y) = point
			if y == len(grid) - 1 and x == len(grid[y]) - 1:
				return path_length((point, remaining)) - 1
			for move in moves(point, remaining):
				if move not in prev:
					frontier.append(move)
					prev[move] = (point, remaining)
		return -1


from collections import deque

def is_valid_cell(row, col, rows, cols):
	return 0 <= row < rows and 0 <= col < cols

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		queue = deque()
		visited = set()
		(rows, cols) = (len(grid), len(grid[0]))
		(start_row, start_col) = (0, 0)
		(end_row, end_col) = (rows - 1, cols - 1)
		queue.append((start_row, start_col, k, 0))
		visited.add((start_row, start_col, k))
		directions = [(1, 0), (0, 1), (0, -1), (-1, 0)]
		while queue:
			(row, col, eliminations, steps) = queue.popleft()
			if row == end_row and col == end_col:
				return steps
			for (dr, dc) in directions:
				(r, c) = (row + dr, col + dc)
				if not is_valid_cell(r, c, rows, cols):
					continue
				if grid[r][c] == 1 and eliminations > 0 and ((r, c, eliminations - 1) not in visited):
					visited.add((r, c, eliminations - 1))
					queue.append((r, c, eliminations - 1, steps + 1))
				if grid[r][c] == 0 and (r, c, eliminations) not in visited:
					visited.add((r, c, eliminations))
					queue.append((r, c, eliminations, steps + 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(n, m) = (len(grid), len(grid[0]))
		heap = [(0, 0, 0, 0)]
		seen = set()
		while heap:
			(c, used, i, j) = heapq.heappop(heap)
			if (i, j, used) in seen:
				continue
			if i == n - 1 and j == m - 1:
				return c
			seen.add((i, j, used))
			for (ni, nj) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
				if 0 <= ni < n and 0 <= nj < m and (used + grid[ni][nj] <= k) and ((ni, nj, used + grid[ni][nj]) not in seen):
					heapq.heappush(heap, (c + 1, used + grid[ni][nj], ni, nj))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if len(grid) == 1 and len(grid[0]) == 1:
			return 0
		q = []
		visited = set((0, 0, 0))
		heapq.heappush(q, (0, 0, (0, 0)))
		while len(q) > 0:
			curr = heapq.heappop(q)
			if curr[2] == (len(grid) - 1, len(grid[0]) - 1):
				return curr[0]
			else:
				for (dx, dy) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
					new_x = curr[2][0] + dx
					new_y = curr[2][1] + dy
					if new_x >= 0 and new_x < len(grid) and (new_y >= 0) and (new_y < len(grid[0])):
						if grid[new_x][new_y] == 1:
							if (curr[1] + 1, new_x, new_y) not in visited and curr[1] + 1 <= k:
								heapq.heappush(q, (curr[0] + 1, curr[1] + 1, (new_x, new_y)))
								visited.add((curr[1] + 1, new_x, new_y))
						elif (curr[1], new_x, new_y) not in visited:
							heapq.heappush(q, (curr[0] + 1, curr[1], (new_x, new_y)))
							visited.add((curr[1], new_x, new_y))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))

		def get_neighbors(i, j):
			neighbors = [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]
			return [(x, y) for (x, y) in neighbors if x >= 0 and x <= m - 1 and (y >= 0) and (y <= n - 1)]
		visited = set()
		frontier = deque([(0, 0, 0)])
		level = 0
		while len(frontier) > 0:
			for i in range(len(frontier)):
				(x, y, obs) = frontier.popleft()
				if x == m - 1 and y == n - 1:
					return level
				if (x, y, obs) not in visited:
					neighbors = get_neighbors(x, y)
					if grid[x][y] == 1:
						if obs == k:
							continue
						else:
							frontier.extend([(x, y, obs + 1) for (x, y) in neighbors])
					else:
						frontier.extend([(x, y, obs) for (x, y) in neighbors])
					visited.add((x, y, obs))
			level += 1
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(R, C) = (len(grid), len(grid[0]))
		q = [(0, 0, 0, k)]
		seen = {}
		while len(q) > 0:
			(i, j, steps, quota) = q.pop(0)
			if i < 0 or i == R or j < 0 or (j == C):
				continue
			if grid[i][j] == 1:
				quota -= 1
			if quota == -1:
				continue
			if i + 1 == R and j + 1 == C:
				return steps
			key = (i, j, quota)
			if key in seen:
				continue
			seen[key] = steps
			q.append((i - 1, j, steps + 1, quota))
			q.append((i + 1, j, steps + 1, quota))
			q.append((i, j - 1, steps + 1, quota))
			q.append((i, j + 1, steps + 1, quota))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(R, C) = (len(grid), len(grid[0]))

		def neighbors(r, c):
			for (nr, nc) in ((r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)):
				if 0 <= nr < R and 0 <= nc < C:
					yield (nr, nc)
		target = (R - 1, C - 1)
		q = deque([((0, 0), 0, k)])
		seen = set()
		while q:
			(node, depth, k) = q.popleft()
			if (node, k) not in seen:
				seen.add((node, k))
				if node == target:
					return depth
				for (r, c) in neighbors(*node):
					if grid[r][c] == 1 and k > 0:
						q.append(((r, c), depth + 1, k - 1))
					elif grid[r][c] == 0:
						q.append(((r, c), depth + 1, k))
		return -1


from collections import deque

def bfs(a, k):
	dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
	if a[0][0] == 1 and k == 0:
		return -1
	q = deque()
	q.append(((0, 0), k - a[0][0], 0))
	visited = set()
	while q:
		(item, k, dist) = q.popleft()
		if (item, k) in visited:
			continue
		if item == (len(a) - 1, len(a[0]) - 1):
			return dist
		visited.add((item, k))
		for dir in dirs:
			x = item[0] + dir[0]
			y = item[1] + dir[1]
			if 0 <= x < len(a) and 0 <= y < len(a[0]):
				if a[x][y] == 0:
					q.append(((x, y), k, dist + 1))
				elif k > 0:
					q.append(((x, y), k - 1, dist + 1))
	return -1

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		return bfs(grid, k)


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		queue = collections.deque([(0, 0, k, 0)])
		visited = set()
		dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]
		if m == 1 and n == 1:
			return 0
		while queue:
			(row, col, elim, steps) = queue.popleft()
			for (x, y) in dirs:
				(new_row, new_col) = (row + x, col + y)
				if 0 <= new_row < m and 0 <= new_col < n:
					if grid[new_row][new_col] == 1 and elim > 0 and ((new_row, new_col, elim + 1) not in visited):
						queue.append((new_row, new_col, elim - 1, steps + 1))
						visited.add((new_row, new_col, elim - 1))
					if grid[new_row][new_col] == 0 and (new_row, new_col, elim) not in visited:
						if new_row == m - 1 and new_col == n - 1:
							return steps + 1
						else:
							queue.append((new_row, new_col, elim, steps + 1))
							visited.add((new_row, new_col, elim))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if not len(grid) or not len(grid[0]):
			return -1
		seen = set()
		m = len(grid)
		n = len(grid[0])

		def validMove(x, y):
			return x >= 0 and y >= 0 and (x < m) and (y < n) and ((x, y) not in seen)
		q = [(0, 0, 0, 0)]
		while q:
			(x, y, z, obs) = q.pop(0)
			if x == m - 1 and y == n - 1:
				return z
			if (x, y, obs) in seen:
				continue
			seen.add((x, y, obs))
			if grid[x][y] == 1 and obs == k:
				continue
			obs += grid[x][y] == 1
			dirs = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
			for d in dirs:
				if validMove(*d):
					(a, b) = d
					q.append((d[0], d[1], z + 1, obs))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(R, C) = (len(grid), len(grid[0]))
		heap = [(0, k, 0, 0)]
		visited = set()
		while heap:
			(l, e, i, j) = heapq.heappop(heap)
			if i == R - 1 and j == C - 1:
				return l
			if e < 0:
				continue
			if (i, j, e) in visited:
				continue
			visited.add((i, j, e))
			for (x, y) in [(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)]:
				if x < 0 or x >= R or y < 0 or (y >= C):
					continue
				heapq.heappush(heap, (l + 1, e - grid[x][y], x, y))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		m = len(grid)
		n = len(grid[0])
		import queue
		queue = queue.Queue()
		queue.put((0, 0, k))
		visited = set([(0, 0, k)])
		steps = 0
		while not queue.empty():
			size = queue.qsize()
			for _ in range(size):
				(x, y, c) = queue.get()
				if x == m - 1 and y == n - 1:
					return steps
				for (delta_x, delta_y) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
					(x_, y_) = (x + delta_x, y + delta_y)
					if x_ < 0 or x_ >= m or y_ < 0 or (y_ >= n):
						continue
					if grid[x_][y_] == 1 and c > 0 and ((x_, y_, c - 1) not in visited):
						queue.put((x_, y_, c - 1))
						visited.add((x_, y_, c - 1))
					if grid[x_][y_] == 0 and (x_, y_, c) not in visited:
						queue.put((x_, y_, c))
						visited.add((x_, y_, c))
			steps += 1
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		m = len(grid)
		n = len(grid[0])
		job_list = deque()

		def def_value():
			return []
		graph = defaultdict(def_value)
		dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

		def inBounds(i, j):
			return 0 <= i and i < m and (0 <= j) and (j < n)
		for i in range(m):
			for j in range(n):
				for dir_pair in dirs:
					next_point_i = i + dir_pair[0]
					next_point_j = j + dir_pair[1]
					if inBounds(next_point_i, next_point_j):
						if grid[next_point_i][next_point_j] == 1:
							graph[i, j].append((next_point_i, next_point_j, 1))
						else:
							graph[i, j].append((next_point_i, next_point_j, 0))
		job_list.append((0, 0, k, 0))
		visited_set = set()
		while len(job_list) > 0:
			cur = job_list.popleft()
			if cur[0] == m - 1 and cur[1] == n - 1:
				return cur[3]
			if (cur[0], cur[1], cur[2]) not in visited_set:
				visited_set.add((cur[0], cur[1], cur[2]))
			else:
				continue
			neighbors = graph[cur[0], cur[1]]
			for neighbor in neighbors:
				if neighbor[2] == 1:
					if cur[2] > 0:
						job_list.append((neighbor[0], neighbor[1], cur[2] - 1, cur[3] + 1))
				else:
					job_list.append((neighbor[0], neighbor[1], cur[2], cur[3] + 1))
		if (m - 1, n - 1) not in visited_set:
			return -1
		else:
			return visited_set[m - 1, n - 1]


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(R, C) = (len(grid), len(grid[0]))
		if R == C == 1:
			return 0
		visited = [[[float('inf') for _ in range(C)] for _ in range(R)] for _ in range(k + 1)]
		q = [(0, k, 0, 0)]
		best = float('inf')
		while q:
			(steps, b, r, c) = heapq.heappop(q)
			if b < 0 or steps >= best:
				continue
			if steps >= visited[b][r][c]:
				continue
			if r == R - 1 and c == C - 1:
				best = min(best, steps)
			visited[b][r][c] = steps
			for (i, j) in ((r + 1, c), (r, c + 1), (r - 1, c), (r, c - 1)):
				if 0 <= i < R and 0 <= j < C and (visited[b - grid[i][j]][i][j] > steps + 1):
					heapq.heappush(q, (steps + 1, b - grid[i][j], i, j))
		res = min((visited[b][R - 1][C - 1] for b in range(k + 1)))
		return res if res != float('inf') else -1


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		M = len(grid)
		N = len(grid[0])
		visited = set()
		q = deque([(0, 0, k, 0)])
		while q:
			data = q.popleft()
			(x, y) = (data[0], data[1])
			k = data[2]
			if (x, y, k) not in visited:
				visited.add((x, y, k))
				if x == M - 1 and y == N - 1:
					return data[3]
				k = data[2]
				steps = data[3]
				for (i, j) in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
					if 0 <= x + i < M and 0 <= y + j < N:
						if grid[x + i][y + j] == 1:
							if k >= 1:
								q.append((x + i, y + j, k - 1, steps + 1))
						else:
							q.append((x + i, y + j, k, steps + 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		heap = []
		heapq.heappush(heap, (0, 0, 0, k))
		m = len(grid)
		n = len(grid[0])
		visited = set()
		while heap:
			(cost, i, j, k) = heapq.heappop(heap)
			if (i, j) == (m - 1, n - 1):
				return cost
			if (i, j, k) in visited:
				continue
			visited.add((i, j, k))
			for (x, y) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
				x_new = x + i
				y_new = y + j
				if 0 <= x_new < m and 0 <= y_new < n:
					if grid[x_new][y_new] == 0:
						heapq.heappush(heap, (cost + 1, x_new, y_new, k))
					elif grid[x_new][y_new] and k:
						heapq.heappush(heap, (cost + 1, x_new, y_new, k - 1))
		return -1


import collections

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		self.g = grid
		visited = set()
		visited.add((0, 0, 0))
		q = collections.deque()
		q.append((0, 0, 0, 0))
		target = (len(grid) - 1, len(grid[0]) - 1)
		while q:
			node = q.popleft()
			if (node[0], node[1]) == target:
				return node[3]
			for n in self.neigh(node):
				nk = node[2] + (1 if grid[n[0]][n[1]] == 1 else 0)
				if (n[0], n[1], nk) not in visited and nk <= k:
					visited.add((n[0], n[1], nk))
					q.append((n[0], n[1], nk, node[3] + 1))
		return -1

	def neigh(self, pos):
		cand = [(pos[0] + 1, pos[1]), (pos[0] - 1, pos[1]), (pos[0], pos[1] + 1), (pos[0], pos[1] - 1)]
		out = []
		for c in cand:
			if c[0] >= 0 and c[0] < len(self.g) and (c[1] >= 0) and (c[1] < len(self.g[0])):
				out.append(c)
		return out


class Solution(object):

	def shortestPath(self, grid, k):
		k -= grid[0][0] == 1
		if k < 0:
			return -1
		(n, m) = (len(grid), len(grid[0]))
		if k >= m + n - 3:
			return m + n - 2
		(n, m) = (n - 1, m - 1)
		bfs = [(0, 0, k)]
		seen = set()
		steps = 0
		while bfs:
			nxt = []
			for (i, j, rem) in bfs:
				if (i, j, rem) in seen:
					continue
				if i == n and j == m:
					return steps
				if i > 0:
					nrem = rem - (grid[i - 1][j] == 1)
					if nrem >= 0:
						nxt.append((i - 1, j, nrem))
				if j > 0:
					nrem = rem - (grid[i][j - 1] == 1)
					if nrem >= 0:
						nxt.append((i, j - 1, nrem))
				if i < n:
					nrem = rem - (grid[i + 1][j] == 1)
					if nrem >= 0:
						nxt.append((i + 1, j, nrem))
				if j < m:
					nrem = rem - (grid[i][j + 1] == 1)
					if nrem >= 0:
						nxt.append((i, j + 1, nrem))
				seen.add((i, j, rem))
			steps += 1
			bfs = nxt
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:

		def dfs(x, y, delete, used, dp):
			if x == len(grid) - 1 and y == len(grid[0]) - 1:
				return 0
			if (x, y, delete) in dp:
				return dp[x, y, delete]
			result = float('inf')
			if 0 <= x < len(grid) and 0 <= y < len(grid[0]):
				if grid[x][y] == 1:
					if delete == 0:
						dp[x, y, delete] = float('inf')
						return float('inf')
					delete -= 1
				used.add((x, y))
				for (dx, dy) in step:
					tx = x + dx
					ty = y + dy
					if (tx, ty) not in used:
						result = min(result, dfs(tx, ty, delete, used, dp) + 1)
				used.remove((x, y))
				dp[x, y, delete] = result
			return result
		shortest = len(grid) + len(grid[0]) - 2
		if k >= shortest:
			return shortest
		step = [[1, 0], [0, 1], [0, -1], [-1, 0]]
		res = dfs(0, 0, k, set(), {})
		return res if res != float('inf') else -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		queue = [[0, 0, 0, k]]
		(row, col) = (len(grid), len(grid[0]))
		visit = set()
		while queue:
			(step, x, y, ob) = heapq.heappop(queue)
			if x == row - 1 and y == col - 1:
				return step
			if (x, y, ob) not in visit:
				visit.add((x, y, ob))
				for (m, n) in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]:
					if 0 <= m < row and 0 <= n < col:
						if not grid[x][y]:
							heapq.heappush(queue, [step + 1, m, n, ob])
						elif ob:
							heapq.heappush(queue, [step + 1, m, n, ob - 1])
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		q = []
		visited = set()
		q.append([0, 0, k - grid[0][0], 0])
		visited.add((0, 0, k - grid[0][0]))
		step = [[1, 0], [-1, 0], [0, 1], [0, -1]]
		n = len(grid)
		m = len(grid[0])
		if n == 1 and m == 1 and (q[0][2] >= 0):
			return 0
		while q:
			now = q.pop(0)
			for i in range(4):
				new = [now[0] + step[i][0], now[1] + step[i][1], 0, now[3] + 1]
				if 0 <= new[0] < n and 0 <= new[1] < m:
					i = new[0]
					j = new[1]
					new[2] = now[2] - grid[i][j]
					if new[2] >= 0 and tuple(new[:3]) not in visited:
						if i == n - 1 and j == m - 1:
							return new[3]
						q.append(new)
						visited.add(tuple(new[:3]))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		cnt = 0
		self.stones = [[0] * n for _ in range(m)]
		cols = [[0] * n for _ in range(m)]
		for i in range(m - 1, -1, -1):
			for j in range(n - 1, -1, -1):
				if i == m - 1 and j == n - 1:
					self.stones[i][j] = grid[i][j]
					cols[i][j] = grid[i][j]
				elif j == n - 1:
					self.stones[i][j] = grid[i][j] + self.stones[i + 1][j]
					cols[i][j] = grid[i][j] + cols[i + 1][j]
				elif i == m - 1:
					self.stones[i][j] = grid[i][j] + self.stones[i][j + 1]
					cols[i][j] = grid[i][j]
				else:
					self.stones[i][j] = grid[i][j] + self.stones[i][j + 1] + cols[i + 1][j]
					cols[i][j] = grid[i][j] + cols[i + 1][j]
		self.memo = {}
		path = self.dfs(grid, 0, 0, k, set([(0, 0, k)]))
		if path == sys.maxsize:
			return -1
		return path

	def dfs(self, grid, x, y, k, visited):
		(m, n) = (len(grid), len(grid[0]))
		if self.stones[x][y] <= k:
			self.memo[x, y, k] = m - 1 - x + (n - 1 - y)
			return self.memo[x, y, k]
		if grid[x][y] == 1:
			k -= 1
		if k < 0:
			return sys.maxsize
		if x == m - 1 and y == n - 1:
			return 0
		if (x, y, k) in self.memo:
			return self.memo[x, y, k]
		directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]
		shortest = sys.maxsize
		for (dx, dy) in directions:
			(nx, ny) = (dx + x, dy + y)
			if nx < 0 or ny < 0 or nx >= m or (ny >= n) or ((nx, ny, k) in visited):
				continue
			visited.add((nx, ny, k))
			shortest = min(shortest, self.dfs(grid, nx, ny, k, visited) + 1)
			visited.remove((nx, ny, k))
		self.memo[x, y, k] = shortest
		return shortest


import queue

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		q = queue.Queue()
		q.put([0, 0, k, 0])
		visited = set()
		dir_ = [[0, 1], [0, -1], [-1, 0], [1, 0]]
		visited.add((0, 0, k))
		while not q.empty():
			(r, c, cur_k, level) = q.get()
			if r == len(grid) - 1 and c == len(grid[0]) - 1:
				return level
			for (x, y) in dir_:
				(nr, nc) = (x + r, y + c)
				if not (0 <= nr < len(grid) and 0 <= nc < len(grid[0])):
					continue
				if grid[nr][nc] == 1 and cur_k > 0 and ((nr, nc, cur_k - 1) not in visited):
					q.put([nr, nc, cur_k - 1, level + 1])
					visited.add((nr, nc, cur_k - 1))
				if grid[nr][nc] == 0 and (nr, nc, cur_k) not in visited:
					q.put([nr, nc, cur_k, level + 1])
					visited.add((nr, nc, cur_k))
				if nr == len(grid) - 1 and nc == len(grid[0]) - 1:
					return level + 1
		return -1


import queue

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		m = len(grid)
		n = len(grid[0])
		if m == n and n == 1:
			return 0
		dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		q = queue.Queue()
		q.put(((0, 0), 0, k))
		vis = set()
		vis.add((0, 0, k))
		while not q.empty():
			((x, y), dist, rem) = q.get()
			for d in dirs:
				(nx, ny) = (x + d[0], y + d[1])
				if 0 <= nx < m and 0 <= ny < n:
					if (nx, ny, rem) in vis:
						continue
					if (nx, ny) == (m - 1, n - 1):
						return dist + 1
					if grid[nx][ny] == 0:
						q.put(((nx, ny), dist + 1, rem))
					elif rem > 0:
						q.put(((nx, ny), dist + 1, rem - 1))
					vis.add((nx, ny, rem))
		return -1

	def shortestPath1(self, grid: List[List[int]], k: int) -> int:
		m = len(grid)
		n = len(grid[0])
		dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		q = queue.Queue()
		q.put(((0, 0), 0))
		while not q.empty():
			((x, y), dist) = q.get()
			for d in dirs:
				(nx, ny) = (x + d[0], y + d[1])
				if 0 <= nx < m and 0 <= ny < n:
					if (nx, ny) == (m - 1, n - 1):
						return dist + 1
					if grid[nx][ny] == 0:
						q.put(((nx, ny), dist + 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		dst = (len(grid) - 1, len(grid[0]) - 1)
		heap = [(0, 0, (0, 0))]
		cost_map = collections.defaultdict(lambda : float('inf'))
		while heap:
			(cost, stop, node) = heapq.heappop(heap)
			if stop > k or cost >= cost_map[stop, node]:
				continue
			if node == dst:
				return cost
			cost_map[stop, node] = cost
			(i, j) = node
			for (n_i, n_j) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
				if n_i < 0 or n_j < 0 or n_i >= m or (n_j >= n):
					continue
				if (n_i, n_j) == dst:
					return cost + 1
				if grid[n_i][n_j] == 0:
					heapq.heappush(heap, (cost + 1, stop, (n_i, n_j)))
				elif stop + 1 <= k:
					heapq.heappush(heap, (cost + 1, stop + 1, (n_i, n_j)))
		return -1


from queue import Queue

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		n = len(grid)
		m = len(grid[0])
		q = Queue()
		if k == 0 and grid[0][0] == 1:
			return -1
		shortest_path = dict()

		def get_neighbors(r, c):
			neighbors = []
			for (ri, ci) in [(r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)]:
				if ri < 0 or ci < 0 or ri == n or (ci == m):
					continue
				neighbors.append((ri, ci))
			return neighbors
		q.put((0, 0, grid[0][0]))
		shortest_path[0, 0, grid[0][0]] = 0
		while q.qsize() > 0:
			(r, c, d) = q.get()
			if r == n - 1 and c == m - 1:
				return shortest_path[r, c, d]
			neighbors = get_neighbors(r, c)
			for (ri, ci) in neighbors:
				if d + grid[r][c] > k or (ri, ci, d + grid[r][c]) in shortest_path:
					continue
				q.put((ri, ci, d + grid[r][c]))
				shortest_path[ri, ci, d + grid[r][c]] = shortest_path[r, c, d] + 1
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		m = len(grid)
		n = len(grid[0])
		min_d = [[math.inf for i in range(n)] for j in range(m)]
		min_d[0][0] = 0
		todo = collections.deque()
		todo.append((0, 0, 0))

		def adjust():
			while todo:
				(x, y, d) = todo.popleft()
				for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
					(nx, ny) = (x + dx, y + dy)
					if 0 <= nx < m and 0 <= ny < n and (grid[nx][ny] == 0) and (min_d[nx][ny] > d + 1):
						min_d[nx][ny] = d + 1
						todo.append((nx, ny, d + 1))
		adjust()
		blockes = []
		for x in range(m):
			for y in range(n):
				if grid[x][y] == 1:
					blockes.append((x, y))
		min_d_to_block = {}
		for i in range(k):
			delay_update = []
			for (x, y) in blockes:
				d = math.inf
				for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
					(nx, ny) = (x + dx, y + dy)
					if 0 <= nx < m and 0 <= ny < n and (min_d[nx][ny] != math.inf):
						d = min(d, min_d[nx][ny] + 1)
				if min_d[x][y] > d:
					delay_update.append((x, y, d))
					todo.append((x, y, d))
			for (x, y, d) in delay_update:
				min_d[x][y] = d
			adjust()
		print(min_d)
		return -1 if min_d[m - 1][n - 1] == inf else min_d[m - 1][n - 1]


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		heap = [[0, -k, 0, 0]]
		seen = set()
		while heap:
			(step, block, i, j) = heappop(heap)
			if (i, j, block) in seen:
				continue
			seen.add((i, j, block))
			if (i, j) == (m - 1, n - 1):
				return step
			for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:
				if 0 <= ni < m and 0 <= nj < n:
					if grid[ni][nj] == 0:
						if (ni, nj, block) not in seen:
							heappush(heap, [step + 1, block, ni, nj])
					elif block + 1 <= 0 and (ni, nj, block + 1) not in seen:
						heappush(heap, [step + 1, block + 1, ni, nj])
		return -1


from heapq import *

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))

		def is_valid(i, j):
			return 0 <= i < m and 0 <= j < n
		directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		bfs = []
		visited = set()
		heappush(bfs, [0, k, (0, 0)])
		while bfs:
			(cur_moves, k_left, pos) = heappop(bfs)
			(i, j) = pos
			if (i, j, k_left) in visited:
				continue
			visited.add((i, j, k_left))
			if pos == (m - 1, n - 1):
				return cur_moves
			for (di, dj) in directions:
				if not is_valid(i + di, j + dj):
					continue
				if grid[i + di][j + dj] == 1 and k_left > 0:
					heappush(bfs, [cur_moves + 1, k_left - 1, (i + di, j + dj)])
				elif grid[i + di][j + dj] == 0:
					heappush(bfs, [cur_moves + 1, k_left, (i + di, j + dj)])
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		steps = 0
		directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

		def checkValid(x, y):
			return 0 <= x < m and 0 <= y < n
		d = {}

		@lru_cache(None)
		def dp(i, j, p):
			nonlocal steps
			if p < 0:
				return float('inf')
			if i == m - 1 and j == n - 1:
				return 0
			d[i, j, p] = min(d.get((i, j, p), float('inf')), steps)
			res = float('inf')
			if steps >= m * n:
				return steps
			for dr in directions:
				(x, y) = (i + dr[0], j + dr[1])
				if x < 0 or x >= m or y < 0 or (y >= n):
					continue
				if grid[x][y] == 0:
					if steps + 1 <= d.get((x, y, p), float('inf')):
						steps += 1
						res = min(res, dp(x, y, p))
						steps -= 1
				elif steps + 1 <= d.get((x, y, p - 1), float('inf')):
					steps += 1
					grid[x][y] = 0
					res = min(res, dp(x, y, p - 1))
					grid[x][y] = 1
					steps -= 1
			return res + 1
		ans = float('inf')
		ans = min(ans, dp(0, 0, k))
		if ans > 10 ** 10:
			return -1
		return ans


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if not grid or not grid[0]:
			return -1
		if k >= len(grid) + len(grid[0]) - 2:
			return len(grid) + len(grid[0]) - 2
		directions = ((0, 1), (0, -1), (-1, 0), (1, 0))
		q = deque([(0, 0, k, 0)])
		visited = set((0, 0, k))
		while q:
			(r, c, obst_rem, steps) = q.popleft()
			for (x, y) in directions:
				(nxt_r, nxt_c) = (r + x, c + y)
				if 0 <= nxt_r < len(grid) and 0 <= nxt_c < len(grid[0]):
					if grid[nxt_r][nxt_c] == 0 and (nxt_r, nxt_c, obst_rem) not in visited or (grid[nxt_r][nxt_c] == 1 and obst_rem > 0 and ((nxt_r, nxt_c, obst_rem - 1) not in visited)):
						if nxt_r == len(grid) - 1 and nxt_c == len(grid[0]) - 1:
							return steps + 1
						else:
							visited.add((nxt_r, nxt_c, obst_rem - grid[nxt_r][nxt_c]))
							q.append((nxt_r, nxt_c, obst_rem - grid[nxt_r][nxt_c], steps + 1))
		return -1


from collections import deque
from heapq import heappush
from heapq import heappop
_DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)]

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if not grid or not grid[0]:
			return 0
		(m, n) = (len(grid), len(grid[0]))
		if k >= m + n - 2:
			return m + n - 2
		queue = []
		visited = set()
		queue.append((0, k, 0, 0))
		visited.add((0, 0, k))
		while queue:
			(cost, ck, ci, cj) = heappop(queue)
			if (ci, cj) == (m - 1, n - 1):
				return cost
			for (di, dj) in _DIRS:
				(newi, newj) = (ci + di, cj + dj)
				if not 0 <= newi < m or not 0 <= newj < n:
					continue
				if grid[newi][newj] == 1 and ck > 0 and ((newi, newj, ck - 1) not in visited):
					heappush(queue, (cost + 1, ck - 1, newi, newj))
					visited.add((newi, newj, ck - 1))
				if grid[newi][newj] == 0 and (newi, newj, ck) not in visited:
					heappush(queue, (cost + 1, ck, newi, newj))
					visited.add((newi, newj, ck))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
		(m, n) = (len(grid), len(grid[0]))
		seen = [[float('inf')] * n for _ in range(m)]
		q = [(0, 0, 0)]
		step = 0
		seen[0][0] = 0
		while q:
			size = len(q)
			for _ in range(size):
				(x, y, o) = q.pop(0)
				if x == m - 1 and y == n - 1:
					return step
				for (dx, dy) in dirs:
					(nx, ny) = (x + dx, y + dy)
					if nx < 0 or ny < 0 or nx >= m or (ny >= n):
						continue
					no = o + grid[nx][ny]
					if no >= seen[nx][ny] or no > k:
						continue
					seen[nx][ny] = no
					q.append((nx, ny, no))
			step += 1
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(M, N) = (len(grid), len(grid[0]))
		if not grid or not grid[0] or (grid[0][0] and k == 0):
			return -1
		minpath = 0
		queue = collections.deque([(0, 0, k)])
		seen = {(0, 0): k}
		while queue:
			for _ in range(len(queue)):
				(i, j, K) = queue.popleft()
				if i == M - 1 and j == N - 1:
					return minpath
				if grid[i][j]:
					K -= 1
				for (r, c) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
					if not 0 <= r < M or not 0 <= c < N or (grid[r][c] and (not K)):
						continue
					if (r, c) in seen and seen[r, c] >= K:
						continue
					seen[r, c] = K
					queue.append((r, c, K))
			minpath += 1
		return -1
		(M, N) = (len(grid), len(grid[0]))
		memo = {}

		def path(i, j, k):
			if not 0 <= i < M or not 0 <= j < N or (grid[i][j] == 1 and k == 0) or (grid[i][j] == -1):
				return float('inf')
			if i == M - 1 and j == N - 1:
				return 0
			if (i, j, k) not in memo:
				if grid[i][j] == 1:
					k -= 1
				(orig, grid[i][j]) = (grid[i][j], -1)
				res = float('inf')
				for (r, c) in [(i + 1, j), (i - 1, j), (i, j - 1), (i, j + 1)]:
					res = min(res, path(r, c, k))
				grid[i][j] = orig
				memo[i, j, k] = res + 1
			return memo[i, j, k]
		min_path = path(0, 0, k)
		return min_path if min_path != float('inf') else -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		queue = deque([[0, 0, 0, 0]])
		(n, m) = (len(grid), len(grid[0]))
		minObs = [0] * n
		move = [[1, 0], [-1, 0], [0, -1], [0, 1]]
		for i in range(n):
			minObs[i] = [1000000000.0] * m
		while len(queue):
			(r, c, obs, steps) = queue.popleft()
			if r == n - 1 and c == m - 1:
				return steps
			for (mR, mC) in move:
				nextR = r + mR
				nextC = c + mC
				if 0 <= nextR < n and 0 <= nextC < m and (obs + grid[nextR][nextC] <= k) and (obs + grid[nextR][nextC] < minObs[nextR][nextC]):
					minObs[nextR][nextC] = obs + grid[nextR][nextC]
					queue.append([nextR, nextC, obs + grid[nextR][nextC], steps + 1])
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		Queue = deque([(0, 0, 0, k)])
		visited = {}
		visited[0, 0] = k
		while Queue:
			(i, j, d, lifeline) = Queue.popleft()
			if i == m - 1 and j == n - 1:
				return d
			for (x, y) in [(i + 1, j), (i - 1, j), (i, j - 1), (i, j + 1)]:
				if x >= 0 and x < m and (y >= 0) and (y < n):
					if grid[x][y] == 1:
						if lifeline > 0 and ((x, y) not in visited or visited[x, y] < lifeline - 1):
							visited[x, y] = lifeline - 1
							Queue.append((x, y, d + 1, lifeline - 1))
					elif (x, y) not in visited or visited[x, y] < lifeline:
						visited[x, y] = lifeline
						Queue.append((x, y, d + 1, lifeline))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(H, W) = (len(grid), len(grid[0]))
		if k >= H + W - 3:
			return H + W - 2
		step = 0
		node_list = [(0, 0, k)]
		visited = set()
		while node_list:
			new_list = []
			for node in node_list:
				if node in visited:
					continue
				visited.add(node)
				(x, y, k_remains) = node
				if x == H - 1 and y == W - 1:
					return step
				for (i, j) in [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]:
					if i < 0 or i >= H or j < 0 or (j >= W):
						continue
					if grid[i][j] == 0:
						new_list.append((i, j, k_remains))
					elif grid[i][j] == 1 and k_remains > 0:
						new_list.append((i, j, k_remains - 1))
			step += 1
			node_list = new_list
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(R, C) = (len(grid), len(grid[0]))
		if R == 1 and C == 1:
			return 0
		cur = [(0, 0, 0, k)]
		step = 0
		seen = {(0, 0): k}
		while cur:
			nex = []
			for (s, r, c, remain) in cur:
				for (rp, cp) in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
					if 0 <= rp < R and 0 <= cp < C:
						if rp == R - 1 and cp == C - 1:
							return s + 1
						next_remain = remain if grid[rp][cp] == 0 else remain - 1
						if next_remain < 0:
							continue
						if seen.get((rp, cp), -1) < next_remain:
							seen[rp, cp] = next_remain
							nex.append((s + 1, rp, cp, next_remain))
			cur = nex
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		seen = [[float('inf')] * len(grid[0]) for _ in range(len(grid))]
		seen[0][0] = 0
		queue = collections.deque([(0, 0, 0)])
		step = 0
		direct = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		while queue:
			length = len(queue)
			for _ in range(length):
				(x, y, u) = queue.popleft()
				if x == len(grid) - 1 and y == len(grid[0]) - 1:
					return step
				for (i, j) in direct:
					(newx, newy, newu) = (i + x, y + j, u)
					if newx < 0 or newy < 0 or newx > len(grid) - 1 or (newy > len(grid[0]) - 1):
						continue
					if grid[newx][newy] == 1:
						newu += 1
					if newu > k or newu >= seen[newx][newy]:
						continue
					seen[newx][newy] = newu
					queue.append((newx, newy, newu))
			step += 1
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		q = collections.deque()
		q.append((0, 0, 0, 0))
		explored = {(0, 0): 0}
		ans = 1 << 31 - 1
		while q:
			(i, j, obs, dist) = q.popleft()
			if i == m - 1 and j == n - 1:
				ans = min(ans, dist)
			for (di, dj) in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
				if 0 <= di < m and 0 <= dj < n:
					if ((di, dj) not in explored or explored[di, dj] > obs + grid[di][dj]) and obs + grid[di][dj] <= k:
						explored[di, dj] = obs + grid[di][dj]
						q.append((di, dj, obs + grid[di][dj], dist + 1))
		return ans if ans < m * n else -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		q = collections.deque([[0, 0, 0]])
		visited = {(0, 0): 0}
		steps = 0
		while q:
			size = len(q)
			for _ in range(size):
				(r, c, obs) = q.popleft()
				if obs > k:
					continue
				if r == m - 1 and c == n - 1:
					return steps
				for (r2, c2) in [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]:
					if 0 <= r2 < m and 0 <= c2 < n:
						next_obs = obs + 1 if grid[r2][c2] == 1 else obs
						if next_obs < visited.get((r2, c2), float('inf')):
							visited[r2, c2] = next_obs
							q.append([r2, c2, next_obs])
			steps += 1
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if not grid:
			return -1
		(m, n) = (len(grid), len(grid[0]))
		visited = defaultdict(int)
		(q, nq, step) = (deque([(0, 0, k)]), deque(), 0)
		while q:
			(x, y, chance) = q.popleft()
			if (x, y) == (m - 1, n - 1):
				return step
			for (dx, dy) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
				(xx, yy) = (x + dx, y + dy)
				if 0 <= xx < m and 0 <= yy < n:
					chance_left = chance - grid[xx][yy]
					if chance_left < 0:
						continue
					if (xx, yy) not in visited or visited[xx, yy] < chance_left:
						visited[xx, yy] = chance_left
						nq.append((xx, yy, chance_left))
			if not q:
				(q, nq) = (nq, deque())
				step += 1
		return -1


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(rows, cols) = (len(grid), len(grid[0]))
		if k >= rows + cols - 3:
			return rows + cols - 2
		(q, seen) = (deque([(0, 0, 0, 0)]), set())
		seen.add((0, 0, 0))
		while q:
			(i, j, rem, curr_path) = q.popleft()
			if i == rows - 1 and j == cols - 1:
				return curr_path
			for (m, n) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
				if 0 <= m < rows and 0 <= n < cols and ((m, n, rem) not in seen) and (rem + grid[m][n] <= k):
					q.append((m, n, rem + grid[m][n], curr_path + 1))
					seen.add((m, n, rem + grid[m][n]))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		d = [(0, 1), (0, -1), (1, 0), (-1, 0)]
		q = collections.deque()
		v = {}
		q.append((0, 0, k, 0))
		while q:
			(x, y, z, s) = q.popleft()
			v[x, y] = z
			if x == m - 1 and y == n - 1:
				return s
			for (dx, dy) in d:
				(nx, ny) = (x + dx, y + dy)
				if nx >= 0 and nx < m and (ny >= 0) and (ny < n) and ((nx, ny) not in v or v[nx, ny] < z - grid[nx][ny]):
					if nx == m - 1 and ny == n - 1:
						return s + 1
					if grid[nx][ny] == 1 and z > 0:
						q.append((nx, ny, z - 1, s + 1))
						v[nx, ny] = z - 1
					elif grid[nx][ny] == 0:
						q.append((nx, ny, z, s + 1))
						v[nx, ny] = z
					else:
						continue
		return -1


MAX = 1601
from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], K: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		maxK = [[-1] * n for _ in range(m)]
		q = deque([(0, 0, 0, K)])
		while q:
			(i, j, d, k) = q.popleft()
			if i == m - 1 and j == n - 1:
				return d
			if k <= maxK[i][j]:
				continue
			maxK[i][j] = max(maxK[i][j], k)
			for (x, y) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
				if 0 <= x < m and 0 <= y < n and (k - grid[x][y] >= 0):
					q.append((x, y, d + 1, k - grid[x][y]))
		return -1


from collections import defaultdict

class Solution:

	def shortestPath(self, A: List[List[int]], k: int) -> int:
		dic = defaultdict(list)
		nbs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		(m, n) = (len(A), len(A[0]))
		st = [(0, 0, 0)]
		target = m * n - 1
		if target == 0:
			return 0
		while st:
			t = []
			for (a, b, c) in st:
				(x, y) = (a // n, a % n)
				for (i, j) in nbs:
					(nx, ny) = (x + i, y + j)
					if 0 <= nx < m and 0 <= ny < n:
						p = nx * n + ny
						cost = c + 1 if A[nx][ny] else c
						if p == target and cost <= k:
							return b + 1
						if p not in dic or cost < dic[p][-1][-1]:
							dic[p].append([b + 1, cost])
							t.append((p, b + 1, cost))
			st = t
		return -1


from queue import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:

		def can_visit(grid, x, y, k, visited, queue, n_steps):
			if grid[x][y] == 0 or k > 0:
				if grid[x][y] > 0:
					k -= 1
				if (x, y) not in visited or k > visited[x, y][0] or n_steps < visited[x, y][1]:
					visited[x, y] = (k, n_steps)
					queue.append((x, y, k, n_steps))
		rows = len(grid)
		cols = len(grid[0])
		x = 0
		y = 0
		queue = deque()
		visited = {}
		n_steps = 0
		visited[x, y] = (k, n_steps)
		queue.append((x, y, k, n_steps))
		min_steps = float(inf)
		while len(queue) > 0:
			(x, y, k_remaining, n_steps) = queue.popleft()
			if x == rows - 1 and y == cols - 1:
				min_steps = min(n_steps, min_steps)
			n_steps += 1
			if x > 0:
				left_x = x - 1
				can_visit(grid, left_x, y, k_remaining, visited, queue, n_steps)
			if y > 0:
				down_y = y - 1
				can_visit(grid, x, down_y, k_remaining, visited, queue, n_steps)
			if x < rows - 1:
				right_x = x + 1
				can_visit(grid, right_x, y, k_remaining, visited, queue, n_steps)
			if y < cols - 1:
				up_y = y + 1
				can_visit(grid, x, up_y, k_remaining, visited, queue, n_steps)
		return min_steps if min_steps != inf else -1


from heapq import heappop, heappush

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if not grid or not grid[0]:
			return -1
		deltas = ((-1, 0), (0, 1), (0, -1), (1, 0))
		(n, m) = (len(grid), len(grid[0]))
		(source, target) = ((0, 0), (n - 1, m - 1))
		queue = deque([(0, source, 0)])
		seen = {source: 0}
		while queue:
			(usedK, currPos, steps) = queue.popleft()
			if currPos == target:
				return steps
			for (delta_x, delta_y) in deltas:
				(x, y) = (currPos[0] + delta_x, currPos[1] + delta_y)
				if x >= 0 and x < n and (y >= 0) and (y < m):
					if (x, y) not in seen or seen[x, y] > usedK:
						if grid[x][y] == 0:
							seen[x, y] = usedK
							queue.append((usedK, (x, y), steps + 1))
						elif usedK < k:
							seen[x, y] = usedK + 1
							queue.append((usedK + 1, (x, y), steps + 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		n = len(grid)
		m = len(grid[0])
		dist = []
		for i in range(n):
			dist.append([])
			for j in range(m):
				dist[i].append([-1, -1])
		queue = []
		queue.append([0, 0, 0, k])
		dist[0][0][0] = 0
		dist[0][0][1] = k
		while queue:
			top = queue.pop(0)
			dis = top[0]
			i = top[1]
			j = top[2]
			if i == n - 1 and j == m - 1:
				return dis
			res = top[3]
			print(i, j, dis, res)
			for (x, y) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
				if x >= 0 and y >= 0 and (x < n) and (y < m):
					nk = res - int(grid[x][y] == 1)
					if nk >= 0:
						if dist[x][y][0] == -1 or nk > dist[x][y][1]:
							dist[x][y][0] = dis + 1
							dist[x][y][1] = nk
							queue.append([dis + 1, x, y, nk])
		return dist[n - 1][m - 1][0]


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		m = len(grid)
		n = len(grid[0])
		path_store = deque([((0, 0), 0, k)])
		seen = {}
		while path_store:
			temp = path_store.pop()
			(s, t) = temp[0]
			if s == m - 1 and t == n - 1:
				return temp[1]
			for (i, j) in [(s + 1, t), (s, t + 1), (s - 1, t), (s, t - 1)]:
				if i < 0 or i >= m or j < 0 or (j >= n) or (k == 0 and grid[i][j] == 1) or (seen.get((i, j), -1) >= temp[2] - (grid[i][j] == 1)):
					continue
				seen[i, j] = temp[2] - (grid[i][j] == 1)
				path_store.appendleft(((i, j), temp[1] + 1, seen[i, j]))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		nodes = deque()
		visited = {}
		nodes.append([(0, 0), k, 0])
		ans = []
		while nodes:
			(x, r, steps) = nodes.popleft()
			if x[0] == len(grid) - 1 and x[1] == len(grid[0]) - 1:
				ans.append(steps)
				break
			if x in visited and visited[x] >= r:
				continue
			visited[x] = r
			if x[0] > 0 and r - grid[x[0] - 1][x[1]] > -1:
				nodes.append([(x[0] - 1, x[1]), r - grid[x[0] - 1][x[1]], steps + 1])
			if x[0] < len(grid) - 1 and r - grid[x[0] + 1][x[1]] > -1:
				nodes.append([(x[0] + 1, x[1]), r - grid[x[0] + 1][x[1]], steps + 1])
			if x[1] > 0 and r - grid[x[0]][x[1] - 1] > -1:
				nodes.append([(x[0], x[1] - 1), r - grid[x[0]][x[1] - 1], steps + 1])
			if x[1] < len(grid[0]) - 1 and r - grid[x[0]][x[1] + 1] > -1:
				nodes.append([(x[0], x[1] + 1), r - grid[x[0]][x[1] + 1], steps + 1])
		if not ans:
			return -1
		return min(ans)


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(dx, dy) = ([1, -1, 0, 0], [0, 0, 1, -1])
		cost = 0
		(this_layer, next_layer) = (1, 0)
		reached = False
		visited = [[-1] * len(grid[0]) for _ in range(len(grid))]
		visited[0][0] = k
		q = deque([(0, 0, k)])
		while q:
			(r, c, p) = q.popleft()
			if r == len(grid) - 1 and c == len(grid[0]) - 1 and (grid[r][c] != 1):
				reached = True
				break
			for i in range(4):
				(x, y) = (c + dx[i], r + dy[i])
				if x < 0 or x >= len(grid[0]) or y < 0 or (y >= len(grid)):
					continue
				k = p - grid[y][x]
				if p <= visited[y][x]:
					continue
				q.append((y, x, k))
				visited[y][x] = k
				next_layer += 1
			this_layer -= 1
			if this_layer == 0:
				this_layer = next_layer
				next_layer = 0
				cost += 1
		if not reached:
			return -1
		return cost


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(rows, cols) = (len(grid), len(grid[0]))
		if rows == 1 and cols == 1:
			return 0
		if k > rows - 1 + cols - 1:
			return rows - 1 + cols - 1
		queue = deque([(0, 0, k)])
		visited = set([(0, 0, k)])
		steps = 0
		while queue:
			nxt = []
			for (r, c, eliminate) in queue:
				for (nr, nc) in [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]:
					if nr >= 0 and nr < rows and (nc >= 0) and (nc < cols):
						if grid[nr][nc] == 1 and eliminate > 0 and ((nr, nc, eliminate - 1) not in visited):
							visited.add((nr, nc, eliminate - 1))
							nxt.append((nr, nc, eliminate - 1))
						if grid[nr][nc] == 0 and (nr, nc, eliminate) not in visited:
							if nr == rows - 1 and nc == cols - 1:
								return steps + 1
							visited.add((nr, nc, eliminate))
							nxt.append((nr, nc, eliminate))
			queue = nxt
			steps += 1
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if len(grid) == 1 and len(grid[0]) == 1:
			return 0 if k >= grid[0][0] else -1
		nextIterations = [(0, 0, k)]
		visited = {}
		count = 0
		while len(nextIterations) > 0:
			newNextIteration = []
			for it in nextIterations:
				directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
				for dir in directions:
					newRow = it[0] + dir[0]
					newCol = it[1] + dir[1]
					if newRow >= 0 and newCol >= 0 and (newRow < len(grid)) and (newCol < len(grid[0])):
						if newRow == len(grid) - 1 and newCol == len(grid[0]) - 1:
							if grid[newRow][newCol] == 0 or it[2] > 0:
								return count + 1
						if it[2] - grid[newRow][newCol] >= 0:
							if (newRow, newCol) not in visited or visited[newRow, newCol] < it[2] - grid[newRow][newCol]:
								newNextIteration.append((newRow, newCol, it[2] - grid[newRow][newCol]))
								visited[newRow, newCol] = it[2] - grid[newRow][newCol]
			count += 1
			nextIterations = newNextIteration
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		queue = deque()
		visited = {}
		queue.append((0, 0, 0, 0))
		while queue:
			(x, y, eliminated, count) = queue.popleft()
			if x == len(grid) - 1 and y == len(grid[0]) - 1:
				return count
			if (x, y) in visited and eliminated >= visited[x, y]:
				continue
			visited[x, y] = eliminated
			for (i, j) in ((0, 1), (1, 0), (0, -1), (-1, 0)):
				(nx, ny) = (x + i, y + j)
				if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and (eliminated + grid[nx][ny] <= k):
					queue.append((nx, ny, eliminated + grid[nx][ny], count + 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		if not grid:
			return -1
		queue = collections.deque([(0, 0, 0)])
		visited = collections.defaultdict(int)
		visited[0, 0] = 0
		dist = 0
		while queue:
			for _ in range(len(queue)):
				(x, y, o) = queue.popleft()
				if o > k:
					continue
				elif (x, y) == (len(grid) - 1, len(grid[0]) - 1):
					return dist
				else:
					directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
					for direction in directions:
						(dx, dy) = direction
						if x + dx < 0 or x + dx >= len(grid) or y + dy < 0 or (y + dy >= len(grid[0])):
							continue
						if grid[x + dx][y + dy] == 1:
							if o + 1 > k or ((x + dx, y + dy) in visited and o + 1 >= visited[x + dx, y + dy]):
								continue
							else:
								queue.append((x + dx, y + dy, o + 1))
								visited[x + dx, y + dy] = o + 1
						elif o > k or ((x + dx, y + dy) in visited and o >= visited[x + dx, y + dy]):
							continue
						else:
							queue.append((x + dx, y + dy, o))
							visited[x + dx, y + dy] = o
			dist += 1
		return -1


class Solution:

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

		def possible(i, j):
			res = []
			for add in direction:
				(i_, j_) = (i + add[0], j + add[1])
				if 0 <= i_ and i_ < H and (0 <= j_) and (j_ < W):
					res.append([i_, j_])
			return res
		queue = [(0, 0, k)]
		step = 0
		q = 0
		K = k
		visited = {}
		visited[0, 0] = k
		if (0, 0) == (H - 1, W - 1):
			return step
		while len(queue) > q:
			step += 1
			size = len(queue) - q
			for _ in range(size):
				(i, j, k) = queue[q]
				q += 1
				for (i_, j_) in possible(i, j):
					if grid[i_][j_] == 0:
						if (i_, j_) not in visited or visited[i_, j_] < k:
							queue.append((i_, j_, k))
							visited[i_, j_] = k
							if i_ == H - 1 and j_ == W - 1:
								return step
					elif k - 1 >= 0:
						if (i_, j_) not in visited or visited[i_, j_] < k - 1:
							queue.append((i_, j_, k - 1))
							visited[i_, j_] = k - 1
							if i_ == H - 1 and j_ == W - 1:
								return step
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(N, M) = (len(grid), len(grid[0]))
		moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
		queue = [(-1, 0, N - 1, M - 1, k)]
		visited = set([(N - 1, M - 1, k)])
		while queue:
			(p, m, i, j, k) = heapq.heappop(queue)
			if i == 0 and j == 0:
				return m
			for move in moves:
				(ni, nj) = (i + move[0], j + move[1])
				if N > ni >= 0 <= nj < M:
					nk = k - grid[ni][nj]
					if nk >= 0 and (ni, nj, nk) not in visited:
						visited.add((ni, nj, nk))
						heapq.heappush(queue, (ni + nj + m + 1, m + 1, ni, nj, nk))
		return -1


from collections import deque

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		num_rows = len(grid)
		num_cols = len(grid[0])
		frontier = deque([(0, 0, 0, k)])
		visited = {}
		while frontier:
			(row, col, dist, chances) = frontier.popleft()
			if chances < 0:
				continue
			if row == num_rows - 1 and col == num_cols - 1:
				return dist
			neighbours = [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]
			for neighbour in neighbours:
				if self.valid_neighbour(neighbour, grid):
					neigh_row = neighbour[0]
					neigh_col = neighbour[1]
					if neighbour not in visited:
						if grid[neigh_row][neigh_col] == 0:
							frontier.append((neigh_row, neigh_col, dist + 1, chances))
							visited[neighbour] = (dist + 1, chances)
						else:
							frontier.append((neigh_row, neigh_col, dist + 1, chances - 1))
							visited[neighbour] = (dist + 1, chances - 1)
					else:
						(last_dist, last_chance) = visited[neighbour]
						if last_chance < chances:
							if grid[neigh_row][neigh_col] == 0:
								frontier.append((neigh_row, neigh_col, dist + 1, chances))
								visited[neighbour] = (dist + 1, chances)
							else:
								frontier.append((neigh_row, neigh_col, dist + 1, chances - 1))
								visited[neighbour] = (dist + 1, chances - 1)
		return -1

	def valid_neighbour(self, neighbour, grid):
		row = neighbour[0]
		col = neighbour[1]
		if row < 0 or row >= len(grid) or col < 0 or (col >= len(grid[row])):
			return False
		return True


import collections

class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		last_blast = collections.defaultdict(lambda : 0)
		visited = set()

		def getN(i, j):
			direction = [[0, 1], [1, 0], [-1, 0], [0, -1]]
			for diff in direction:
				(i_diff, j_diff) = diff
				curr_i = i + i_diff
				curr_j = j + j_diff
				if curr_i < 0 or curr_j < 0 or curr_i >= len(grid) or (curr_j >= len(grid[0])):
					continue
				yield [curr_i, curr_j]
		node_to_trav = deque()
		node_to_trav.append((0, 0, k))
		min_steps = -1
		while node_to_trav:
			trav_length = len(node_to_trav)
			min_steps += 1
			for i in range(trav_length):
				curr_node = node_to_trav.popleft()
				(i, j, r_dyno) = curr_node
				visited.add((i, j))
				if i == len(grid) - 1 and j == len(grid[0]) - 1:
					return min_steps
				for n in getN(i, j):
					(n_i, n_j) = n
					if grid[n_i][n_j] == 0:
						if (n_i, n_j, r_dyno) not in visited:
							node_to_trav.append((n_i, n_j, r_dyno))
							visited.add((n_i, n_j, r_dyno))
					elif r_dyno > last_blast[n_i, n_j]:
						if (n_i, n_j, r_dyno - 1) not in visited:
							node_to_trav.append((n_i, n_j, r_dyno - 1))
							last_blast[n_i, n_j] = r_dyno - 1
							visited.add((n_i, n_j, r_dyno - 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		m = len(grid)
		n = len(grid[0])
		dp = defaultdict(lambda : float('inf'))
		dp[m - 1, n - 1, k] = 0
		todo = [(m - 1, n - 1, k)]
		seen = {(m - 1, n - 1): k}
		while todo:
			new = []
			for (i, j, r) in todo:
				if (i, j) == (0, 0):
					return dp[i, j, r]
				for (x, y) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
					if 0 <= x < m and 0 <= y < n and (grid[x][y] == 0 or r > 0):
						new_r = r if grid[x][y] == 0 else r - 1
						dp[x, y, new_r] = min(dp[x, y, new_r], dp[i, j, r] + 1)
						if (x, y) not in seen or seen[x, y] < new_r:
							new.append((x, y, new_r))
							seen[x, y] = new_r
			todo = new
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(R, C) = (len(grid), len(grid[0]))
		if R == 1 and C == 1:
			return 0
		if k >= R - 1 + C - 1:
			return R - 1 + C - 1
		q = collections.deque([(0, 0, k, 0)])
		seen = set([(0, 0, k)])
		while q:
			(i, j, left, steps) = q.popleft()
			for (new_i, new_j) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
				if 0 <= new_i < R and 0 <= new_j < C:
					if grid[new_i][new_j] == 1 and left > 0 and ((new_i, new_j, left - 1) not in seen):
						seen.add((new_i, new_j, left - 1))
						q.append((new_i, new_j, left - 1, steps + 1))
					elif grid[new_i][new_j] == 0 and (new_i, new_j, left) not in seen:
						if new_i == R - 1 and new_j == C - 1:
							return steps + 1
						seen.add((new_i, new_j, left))
						q.append((new_i, new_j, left, steps + 1))
		return -1


class Solution:

	def shortestPath(self, grid: List[List[int]], k: int) -> int:
		(m, n) = (len(grid), len(grid[0]))
		MAX_DIST = m * n
		shortest = MAX_DIST
		visited = set([])
		visited.add((m - 1, n - 1, k, 0))

		def dfs(i, j, k, steps):
			nonlocal shortest
			if (i, j) == (0, 0):
				shortest = min(shortest, steps)
				return
			if grid[i][j] == 1:
				k -= 1
				if k < 0:
					return
			if grid[i][j] == 2:
				return
			if shortest <= steps + i + j:
				return
			(grid[i][j], save) = (2, grid[i][j])
			for (x, y) in ((i - 1, j), (i, j - 1), (i + 1, j), (i, j + 1)):
				if m > x >= 0 <= y < n and (x, y, k, steps + 1) not in visited:
					visited.add((x, y, k, steps + 1))
					dfs(x, y, k, steps + 1)
			grid[i][j] = save
		dfs(m - 1, n - 1, k, 0)
		return shortest if shortest != MAX_DIST else -1