Given a 2-D binary matrix of size n*m, where 0 represents an empty space while 1 represents a wall you cannot walk through. You are also given an integer k.
You can walk up, down, left, or right. Given that you can remove up to k walls, return the minimum number of steps to walk from the top left corner (0, 0) to the bottom right corner (n-1, m-1).
Note: If there is no way to walk from the top left corner to the bottom right corner, return -1.
Example 1:
Input: n = 3, m = 3, k = 1
mat = {{0, 0, 0},
       {0, 0, 1},
       {0, 1, 0}}
Output:
4
Explanation:
We can remove any one of the walls and
reach the bottom in 4 moves.  
Example 2:
Input:
n = 2, m = 2, k = 0
mat[] = {{0, 1},
         {1, 0}}
Output:
-1
Explanation:
There's no way of reaching the bottom
corner without removing any walls.
Your Task:
The task is to complete the function shotestPath() which takes three integers n, m, and k and also a matrix of size n*m as input and returns the minimum number of steps to walk from the top left corner to the bottom right corner.
Constraints:
1 ≤ n,m ≤ 50
0 ≤ k ≤ n*m
Top left and bottom right corners doesn't have 1
Expected Time Complexity: O(n*m*k).
Expected Auxiliary Space: O(n*m*k).

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Matrices

Data structures

Graph traversal

Starter code: #User function Template for python3



class Solution:

    def shotestPath(self, mat, n, m, k):

        # code here 

Solutions:
from collections import deque

class Solution:

	def shotestPath(self, mat, m, n, k):
		(m, n) = (len(mat), len(mat[0]))
		q = deque([(0, 0, k, 0)])
		visited = set()
		if k >= m + n - 2:
			return m + n - 2
		while q:
			(row, col, obstacles, steps) = q.popleft()
			if row == m - 1 and col == n - 1:
				return steps
			for (r, c) in ((row, col + 1), (row + 1, col), (row - 1, col), (row, col - 1)):
				if 0 <= r < m and 0 <= c < n:
					k_rem = obstacles - mat[r][c]
					if mat[r][c] >= 0 and k_rem >= 0 and ((r, c, k_rem) not in visited):
						q.append((r, c, k_rem, steps + 1))
						visited.add((r, c, k_rem))
		return -1


from queue import Queue

class Solution:

	def shotestPath(self, mat, n, m, k):
		adjs = [1, 0, -1, 0, 1]
		visited = [[float('inf') for _ in range(m)] for _ in range(n)]
		visited[0][0] = 0
		q = Queue()
		q.put((0, 0, 0))
		while not q.empty():
			(r, c, d) = q.get()
			if r == n - 1 and c == m - 1:
				return d
			for i in range(4):
				(ad_r, ad_c) = (r + adjs[i], c + adjs[i + 1])
				if ad_r < 0 or ad_r == n or ad_c < 0 or (ad_c == m):
					continue
				(ad_d, ad_b) = (d + 1, visited[r][c])
				if mat[ad_r][ad_c] == 1:
					ad_b += 1
				if k < ad_b:
					continue
				if ad_b < visited[ad_r][ad_c]:
					visited[ad_r][ad_c] = ad_b
					q.put((ad_r, ad_c, ad_d))
		return -1


from collections import deque

def solve(visited, mat, n, m, K, di, dj):
	q = deque([(0, 0, 0, 0)])
	visited[0][0] = 0
	while q:
		(k, i, j, steps) = q.popleft()
		if i == n - 1 and j == m - 1:
			return steps
		for l in range(4):
			(x, y) = (i + di[l], j + dj[l])
			if 0 <= x < n and 0 <= y < m:
				new_k = k + mat[x][y]
				if new_k > K:
					continue
				if visited[x][y] == -1 or new_k < visited[x][y]:
					q.append((new_k, x, y, steps + 1))
					visited[x][y] = new_k
	return -1

class Solution:

	def shotestPath(self, mat, n, m, K):
		(n, m) = (len(mat), len(mat[0]))
		di = [-1, 0, 1, 0]
		dj = [0, 1, 0, -1]
		visited = [[-1 for j in range(m)] for i in range(n)]
		return solve(visited, mat, n, m, K, di, dj)


from collections import deque

class Solution:

	def shotestPath(self, mat, n, m, k):
		visited = [[-1 for j in range(m)] for i in range(n)]
		de = deque()
		de.append([0, 0, 0, k])
		while len(de):
			temp = de.popleft()
			row = temp[0]
			col = temp[1]
			steps = temp[2]
			rem_k = temp[3]
			if row < 0 or row >= n or col < 0 or (col >= m):
				continue
			if row == n - 1 and col == m - 1:
				return steps
			if mat[row][col] == 1:
				if rem_k <= 0:
					continue
				else:
					rem_k -= 1
			if visited[row][col] != -1 and rem_k <= visited[row][col]:
				continue
			visited[row][col] = rem_k
			de.append([row, col + 1, steps + 1, rem_k])
			de.append([row, col - 1, steps + 1, rem_k])
			de.append([row + 1, col, steps + 1, rem_k])
			de.append([row - 1, col, steps + 1, rem_k])
		return -1


from collections import deque
import math

class Solution:

	def isSafe(self, r, c, R, C, vis, key):
		return r >= 0 and r < R and (c >= 0) and (c < C) and (not key in vis)

	def shotestPath(self, grid, n, m, k):
		if len(grid) == len(grid[0]) == 1:
			return 0
		start = (0, 0, grid[0][0], 0)
		visited = {}
		q = deque((start,))
		while q:
			(r, c, ct, turn) = q.popleft()
			nxt = [(r, c - 1), (r - 1, c), (r + 1, c), (r, c + 1)]
			for (r2, c2) in nxt:
				if 0 <= r2 < n and 0 <= c2 < m:
					ct2 = ct + grid[r2][c2]
					nn = (r2, c2, ct2, turn + 1)
					if ct2 <= k and (r2, c2) == (n - 1, m - 1):
						return turn + 1
					kk = (r2, c2)
					if ct2 <= k and visited.get(kk, math.inf) > ct2:
						visited[kk] = ct2
						q.append(nn)
		return -1


from collections import deque, defaultdict

class Solution:

	def shotestPath(self, mat, n, m, k):
		moves = [(0, -1), (0, 1), (1, 0), (-1, 0)]
		q = deque({(0, 0, 1 if mat[0][0] else 0, 0)})
		mem = {(0, 0): 1 if mat[0][0] else 0}
		min_steps = float('inf')
		while q:
			s = len(q)
			for _ in range(s):
				(x, y, kx, st) = q.popleft()
				if (x, y) == (n - 1, m - 1):
					min_steps = min(min_steps, st)
					continue
				for (dx, dy) in moves:
					(r, c) = (x + dx, y + dy)
					if 0 <= r < n and 0 <= c < m:
						kxx = kx + 1 if mat[r][c] else kx
						if kxx <= k and ((r, c) in mem and mem[r, c] > kxx or (r, c) not in mem):
							q.append((r, c, kxx, st + 1))
							mem[r, c] = kxx
		return -1 if min_steps == float('inf') else min_steps


from collections import deque

class Solution:

	def shotestPath(self, M, R, C, k):
		if R + C - 2 <= k:
			return R + C - 2
		q = deque([(0, 0, 0, k)])
		v = set((0, 0, k))
		while q:
			(r, c, steps, k) = q.popleft()
			if (r, c) == (R - 1, C - 1):
				return steps
			for (nr, nc) in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
				if nr < 0 or nr == R or nc < 0 or (nc == C):
					continue
				nk = k - (M[nr][nc] == 1)
				if nk < 0:
					continue
				if (nr, nc, nk) in v:
					continue
				v.add((nr, nc, nk))
				q.append((nr, nc, steps + 1, nk))
		return -1


from collections import deque

class Solution:

	def shotestPath(self, mat, rows, cols, K):
		directions = [(0, 1), (-1, 0), (0, -1), (1, 0)]
		q = deque()
		q.append((0, 0, 0, 0))
		vis = [[float('inf') for a in range(cols + 1)] for a in range(rows + 1)]
		vis[0][0] = 0
		minD = -1
		while len(q) > 0:
			(i, j, d, k) = q.popleft()
			if i == rows - 1 and j == cols - 1:
				minD = d
				return minD
			for (iD, jD) in directions:
				(iN, jN) = (i + iD, j + jD)
				if 0 <= iN < rows and 0 <= jN < cols:
					newK = k + mat[iN][jN]
					if newK <= K and vis[iN][jN] > newK:
						q.append((iN, jN, d + 1, newK))
						vis[iN][jN] = newK
		return minD


from collections import deque

def solve(mat, n, m, K, visited):
	q = deque([(0, 0, 0, 0)])
	while q:
		(i, j, k, steps) = q.popleft()
		if i < 0 or j < 0 or i > n - 1 or (j > m - 1):
			continue
		if i == n - 1 and j == m - 1:
			return steps
		k = k + mat[i][j]
		if k > K:
			continue
		if visited[i][j] != -1 and visited[i][j] <= k:
			continue
		visited[i][j] = k
		q.append((i - 1, j, k, steps + 1))
		q.append((i, j + 1, k, steps + 1))
		q.append((i + 1, j, k, steps + 1))
		q.append((i, j - 1, k, steps + 1))
	return -1

class Solution:

	def shotestPath(self, mat, n, m, k):
		(n, m) = (len(mat), len(mat[0]))
		visited = [[-1 for j in range(m)] for i in range(n)]
		return solve(mat, n, m, k, visited)


class Solution:

	def shotestPath(self, mat, n, m, k):
		v = []
		for i in range(n):
			v.append([])
			for j in range(m):
				v[i].append([m * n * 10] * (k + 1))
		if n == 1 and m == 1:
			return 0
		q = [(0, 0, k, 0)]
		v[0][0][k] = 1
		while q:
			(x, y, curK, step) = q.pop(0)
			for (a, b) in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
				if 0 <= a < n and 0 <= b < m and (mat[a][b] <= curK) and (v[a][b][curK - mat[a][b]] == m * n * 10):
					if a == n - 1 and b == m - 1:
						return step + 1
					if step + 1 < min(v[a][b][curK - mat[a][b]:]):
						v[a][b][curK - mat[a][b]] = step + 1
						q.append((a, b, curK - mat[a][b], step + 1))
		return -1


import collections

class Solution:

	def shotestPath(self, mat, m, n, k):
		(q, seen) = ([(0, 0, k, 0)], collections.defaultdict(lambda : -1))
		seen[0, 0] = k
		for (i, j, r, h) in q:
			if (i, j) == (m - 1, n - 1):
				return h
			if r < 0:
				continue
			for (x, y) in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
				if m > x >= 0 <= y < n and seen[x, y] < r - mat[x][y]:
					seen[x, y] = r - mat[x][y]
					q += ((x, y, r - mat[x][y], h + 1),)
		return -1


from collections import deque

class Solution:

	def shotestPath(self, mat, n, m, k):
		if len(mat) == 1 and len(mat[0]) == 1:
			return 0
		q = deque([(0, 0, k, 0)])
		visited = set([(0, 0, k)])
		if len(mat) - 1 + (len(mat[0]) - 1) < k:
			return len(mat) - 1 + (len(mat[0]) - 1)
		while q:
			(r, c, e, steps) = q.popleft()
			for (new_r, new_c) in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
				if new_r >= 0 and new_r < len(mat) and (new_c >= 0) and (new_c < len(mat[0])):
					if mat[new_r][new_c] == 1 and e > 0 and ((new_r, new_c, e - 1) not in visited):
						visited.add((new_r, new_c, e - 1))
						q.append((new_r, new_c, e - 1, steps + 1))
					if mat[new_r][new_c] == 0 and (new_r, new_c, e) not in visited:
						if new_r == len(mat) - 1 and new_c == len(mat[0]) - 1:
							return steps + 1
						visited.add((new_r, new_c, e))
						q.append((new_r, new_c, e, steps + 1))
		return -1


from collections import deque

class Solution:

	def shotestPath(self, mat, n, m, k):
		(n, m) = (len(mat), len(mat[0]))
		q = deque([(0, 0, k, 0)])
		visited = set()
		if k >= m + n - 2:
			return m + n - 2
		while q:
			(i, j, k, steps) = q.popleft()
			if i == n - 1 and j == m - 1:
				return steps
			neighbors = [(i, j + 1), (i + 1, j), (i - 1, j), (i, j - 1)]
			for (n_i, n_j) in neighbors:
				if 0 <= n_i < n and 0 <= n_j < m:
					n_k = k - mat[n_i][n_j]
					n_steps = steps + 1
					if n_k >= 0 and (n_i, n_j, n_k) not in visited:
						q.append((n_i, n_j, n_k, n_steps))
						visited.add((n_i, n_j, n_k))
		return -1


import sys
from collections import deque
from queue import PriorityQueue

class Solution:

	def shotestPath(self, mat, n, m, k):
		vis = []
		for i in range(n):
			vis.append([(sys.maxsize, sys.maxsize)] * m)
		vis[0][0] = (mat[0][0], 0)
		pq = PriorityQueue()
		pq.put((0, 0, (0, 0)))
		dr = [-1, +1, 0, 0]
		dc = [0, 0, -1, +1]
		ans = sys.maxsize
		while pq.empty() != True:
			(dis, wall, node) = pq.get()
			(r, c) = node
			if wall > k:
				continue
			for i in range(4):
				row = r + dr[i]
				col = c + dc[i]
				if row >= 0 and row < n and (col >= 0) and (col < m):
					(w, adj) = vis[row][col]
					if dis + 1 < w:
						vis[row][col] = (dis + 1, wall + mat[row][col])
						pq.put((dis + 1, wall + mat[row][col], (row, col)))
		if vis[n - 1][m - 1][0] >= sys.maxsize:
			return -1
		return vis[n - 1][m - 1][0]


class Solution:

	def shotestPath(self, mat, n, m, k):
		from collections import deque
		if n == 1 and m == 1:
			return 0
		if k >= m + n - 2:
			return m + n - 2
		visited = set((0, 0, 0))
		queue = deque([(0, 0, 0, 0)])
		dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
		while queue:
			(steps, rmv, x, y) = queue.popleft()
			if x == n - 1 and y == m - 1 and (rmv <= k):
				return steps
			elif rmv <= k:
				for dir in dirs:
					x_new = x + dir[0]
					y_new = y + dir[1]
					if x_new < 0 or y_new < 0 or x_new == n or (y_new == m):
						continue
					rmv_new = rmv + mat[x_new][y_new]
					if rmv_new <= k and (x_new, y_new, rmv_new) not in visited:
						queue.append((steps + 1, rmv_new, x_new, y_new))
						visited.add((x_new, y_new, rmv_new))
		return -1


class Solution:

	def shotestPath(self, mat, n, m, k):
		from collections import deque
		if k >= m + n - 2:
			return m + n - 2
		if m - 1 == 0 and n - 1 == 0:
			return 0
		visited = set((0, 0, 0))
		queue = deque([(0, 0, 0, 0)])
		while queue:
			(steps, rmv, x, y) = queue.popleft()
			if x == n - 1 and y == m - 1 and (rmv <= k):
				return steps
			elif rmv <= k:
				if x != 0:
					rmv_new = rmv + mat[x - 1][y]
					if rmv_new <= k and (x - 1, y, rmv_new) not in visited:
						queue.append((steps + 1, rmv_new, x - 1, y))
						visited.add((x - 1, y, rmv_new))
				if y != 0:
					rmv_new = rmv + mat[x][y - 1]
					if rmv_new <= k and (x, y - 1, rmv_new) not in visited:
						queue.append((steps + 1, rmv_new, x, y - 1))
						visited.add((x, y - 1, rmv_new))
				if x != n - 1:
					rmv_new = rmv + mat[x + 1][y]
					if rmv_new <= k and (x + 1, y, rmv_new) not in visited:
						queue.append((steps + 1, rmv_new, x + 1, y))
						visited.add((x + 1, y, rmv_new))
				if y != m - 1:
					rmv_new = rmv + mat[x][y + 1]
					if rmv_new <= k and (x, y + 1, rmv_new) not in visited:
						queue.append((steps + 1, rmv_new, x, y + 1))
						visited.add((x, y + 1, rmv_new))
		return -1


class Solution:

	def shotestPath(self, mat, n, m, k):
		from collections import deque
		target = (n - 1, m - 1)
		directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]
		queue = deque([(0, 0, 0, 0)])
		seen = set([0, 0, 0])
		if k >= m + n - 2:
			return m + n - 2
		if m - 1 == 0 and n - 1 == 0:
			return 0
		while queue:
			(steps, i, j, eliminated) = queue.popleft()
			if (i, j) == target:
				return steps
			for (x, y) in directions:
				(new_x, new_y) = (x + i, y + j)
				if new_x < 0 or new_y < 0 or new_x > n - 1 or (new_y > m - 1) or (eliminated + mat[new_x][new_y] > k) or ((new_x, new_y, eliminated) in seen):
					continue
				seen.add((new_x, new_y, eliminated))
				queue.append([steps + 1, new_x, new_y, eliminated + mat[new_x][new_y]])
		return -1


from collections import deque

class Solution:

	def shotestPath(self, grid, n, m, k):
		if len(grid) == 1 and len(grid[0]) == 1:
			return 0
		n = len(grid)
		m = len(grid[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))
		dx = [0, 0, 1, -1]
		dy = [1, -1, 0, 0]
		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 < n and (new_col >= 0) and (new_col < m):
					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 == n - 1 and new_col == m - 1:
							return steps + 1
						visited.add((new_row, new_col, eliminate))
						queue.append((new_row, new_col, eliminate, steps + 1))
		return -1


from collections import deque

class Solution:

	def shotestPath(self, a, n, m, k):
		if len(a) == 1 and len(a[0]) == 1:
			return 0
		if k > len(a) - 1 + len(a[0]) - 1:
			return len(a) - 1 + len(a[0]) - 1
		q = deque([(0, 0, k, 0)])
		visited = set((0, 0, k))
		dx = [0, 0, 1, -1]
		dy = [1, -1, 0, 0]
		n = len(a)
		m = len(a[0])
		while q:
			(x, y, k, s) = q.popleft()
			for i in range(4):
				newx = x + dx[i]
				newy = y + dy[i]
				if newx >= 0 and newx < n and (newy >= 0) and (newy < m):
					if a[newx][newy] == 1 and k > 0 and ((newx, newy, k - 1) not in visited):
						q.append((newx, newy, k - 1, s + 1))
						visited.add((newx, newy, k - 1))
					if a[newx][newy] == 0 and (newx, newy, k) not in visited:
						if newx == n - 1 and newy == m - 1:
							return s + 1
						visited.add((newx, newy, k))
						q.append((newx, newy, k, s + 1))
		return -1


from collections import deque
safe = lambda i, j: -1 < i < n and -1 < j < m

class Solution:

	def shotestPath(self, mat, n, m, k):
		if n == 1 and m == 1:
			return 0
		q = deque([(0, 0, k, 0)])
		vis = [[-1] * m for _ in range(n)]
		vis[0][0] = k
		choices = [(0, 1), (1, 0), (-1, 0), (0, -1)]
		while len(q):
			(i, j, k, d) = q.popleft()
			neigh = [(i + di, j + dj) for (di, dj) in choices]
			for (i2, j2) in neigh:
				d2 = d + 1
				if not safe(i2, j2):
					continue
				k2 = k - mat[i2][j2]
				if i2 == n - 1 and j2 == m - 1:
					return d2
				if k2 >= 0 and vis[i2][j2] < k2:
					vis[i2][j2] = k2
					q.append((i2, j2, k2, d2))
		return -1


from collections import deque
from copy import deepcopy

def matrix(init, *dimensions):
	if len(dimensions) == 0:
		return None
	ans = [deepcopy(init) for _ in range(dimensions[-1])]
	for d in dimensions[-2::-1]:
		ans = [deepcopy(ans) for _ in range(d)]
	return ans
safe = lambda i, j: -1 < i < n and -1 < j < m

class Solution:

	def shotestPath(self, mat, n, m, k):
		if n == 1 and m == 1:
			return 0
		q = deque([(0, 0, k, 0)])
		vis = matrix(-1, n, m)
		vis[0][0] = k
		choices = [(0, 1), (1, 0), (-1, 0), (0, -1)]
		while len(q):
			(i, j, k, d) = q.popleft()
			neigh = [(i + di, j + dj) for (di, dj) in choices]
			for (i2, j2) in neigh:
				d2 = d + 1
				if not safe(i2, j2):
					continue
				k2 = k - mat[i2][j2]
				if i2 == n - 1 and j2 == m - 1:
					return d2
				if k2 >= 0 and vis[i2][j2] < k2:
					vis[i2][j2] = k2
					q.append((i2, j2, k2, d2))
		return -1


class Solution:

	def shotestPath(self, mat, n, m, k):
		import sys
		from collections import deque
		q = deque([(0, 0, 0, 0)])
		vis = set([(0, 0, k)])
		dx = [0, 0, 1, -1]
		dy = [1, -1, 0, 0]
		ans = sys.maxsize
		while q:
			(x, y, qk, dis) = q.popleft()
			if x == n - 1 and y == m - 1:
				ans = min(ans, dis)
				return ans
			if k > n - 1 + m - 1:
				return n - 1 + m - 1
			for i in range(4):
				newx = x + dx[i]
				newy = y + dy[i]
				if newx >= 0 and newx < n and (newy >= 0) and (newy < m):
					newk = qk + mat[newx][newy]
					if newk <= k and (newx, newy, newk) not in vis:
						vis.add((newx, newy, newk))
						q.append((newx, newy, newk, dis + 1))
		return -1


class Solution:

	def shotestPath(self, grid, n, m, k):
		start = (0, 0, k)
		q = [start]
		visited = {(0, 0): k}
		steps = 0
		while q:
			nq = []
			for (r0, c0, k0) in q:
				if r0 == n - 1 and c0 == m - 1:
					return steps
				nk = k0 - grid[r0][c0]
				if nk < 0:
					continue
				for (dr, dc) in ((1, 0), (-1, 0), (0, 1), (0, -1)):
					r = r0 + dr
					c = c0 + dc
					if r < 0 or r >= n or c < 0 or (c >= m):
						continue
					if (r, c) not in visited or visited[r, c] < nk:
						visited[r, c] = nk
						nq.append((r, c, nk))
			steps += 1
			q = nq
		return -1