Given a path in the form of a rectangular matrix having few landmines arbitrarily placed (marked as 0), calculate length of the shortest safe route possible from any cell in the first column to any cell in the last column of the matrix. We have to avoid landmines and their four adjacent cells (left, right, above and below) as they are also unsafe. We are allowed to move to only adjacent cells which are not landmines. i.e. the route cannot contains any diagonal moves.
 
Example 1:
Input:
[1 0 1 1 1]
[1 1 1 1 1]
[1 1 1 1 1]
[1 1 1 0 1]
[1 1 1 1 0]
Output: 6
Explanation: 
We can see that length of shortest
safe route is 13 (Highlighted in Bold).
[1 0 1 1 1]
[1 1 1 1 1] 
[1 1 1 1 1]
[1 1 1 0 1] 
[1 1 1 1 0]
Example 2:
Input:
[1 1 1 1 1]
[1 1 0 1 1]
[1 1 1 1 1]
Output: -1
Explanation: There is no possible path from
first column to last column.
Your Task:
You don't need to read input or print anything. Your task is to complete the function findShortestPath() which takes matrix as input parameter and return an integer denoting the shortest path. If there is no possible path, return -1. 
Expected Time Complexity: O(R * C)
Expected Auxiliary Space: O(1)
Constraints:
1 <= R,C <= 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Graph traversal

Starter code: from typing import List





from typing import List





class Solution:

    def findShortestPath(self, mat : List[List[int]]) -> int:

        # code here

        



Solutions:
from typing import List
from typing import List

class Solution:

	def findShortestPath(self, mat: List[List[int]]) -> int:
		(n, m) = (len(mat), len(mat[0]))
		dr = [(-1, 0), (0, 1), (1, 0), (0, -1)]

		def outBounds(i, j):
			if i <= -1 or i >= n or j <= -1 or (j >= m):
				return True
			return False

		def isSafe(i, j):
			if outBounds(i, j) or mat[i][j] == 0:
				return False
			for d in dr:
				(x, y) = (i + d[0], j + d[1])
				if not outBounds(x, y) and mat[x][y] == 0:
					return False
			return True

		def rec(i, j):
			if memo[i][j] != -1 and memo[i][j] != float('inf'):
				return memo[i][j]
			if j == m - 1:
				return 1
			visited.add((i, j))
			min_ = float('inf')
			for d in dr:
				if d == (0, -1):
					continue
				(x, y) = (i + d[0], j + d[1])
				if (x, y) not in visited and isSafe(x, y):
					min_ = min(min_, 1 + rec(x, y))
			memo[i][j] = min_
			visited.remove((i, j))
			return memo[i][j]
		visited = set()
		memo = [[-1 for j in range(m)] for i in range(n)]
		min_ = float('inf')
		for i in range(n):
			if isSafe(i, 0):
				min_ = min(min_, rec(i, 0))
		return -1 if min_ == float('inf') else min_


from typing import List

class Solution:

	def findShortestPath(self, mat: List[List[int]]) -> int:
		(n, m) = (len(mat), len(mat[0]))
		dr = [(-1, 0), (0, 1), (1, 0), (0, -1)]
		visited = set()

		def outBounds(i, j):
			if i <= -1 or i >= n or j <= -1 or (j >= m):
				return True
			return False

		def isSafe(i, j):
			if outBounds(i, j) or mat[i][j] == 0:
				return False
			return True
		landmines = []
		for i in range(n):
			for j in range(m):
				if mat[i][j] == 0:
					landmines.append((i, j))
		for (i, j) in landmines:
			for d in dr:
				(x, y) = (i + d[0], j + d[1])
				if not outBounds(x, y):
					mat[x][y] = 0
		q = []
		for i in range(n):
			if isSafe(i, 0):
				visited.add((i, 0))
				q.append((i, 0, 1))
		while q:
			(i, j, step) = q.pop(0)
			if j == m - 1:
				return step
			for d in dr:
				(x, y) = (i + d[0], j + d[1])
				if isSafe(x, y) and (x, y) not in visited:
					q.append((x, y, step + 1))
					visited.add((x, y))
		return -1


from typing import List
from typing import List
from collections import deque

class Solution:

	def findShortestPath(self, mat: List[List[int]]) -> int:
		(n, m) = (len(mat), len(mat[0]))
		d = [1, -1, 0, 0]
		for i in range(n):
			for j in range(m):
				if mat[i][j] == 0:
					for k in range(4):
						(x, y) = (i + d[k], j + d[3 - k])
						if x >= 0 and x < n and (y >= 0) and (y < m) and (mat[x][y] == 1):
							mat[x][y] = 2
		q = deque()
		for i in range(n):
			if mat[i][0] == 1:
				mat[i][0] = 2
				q.append((i, 0))
		ans = 1
		while q:
			s = len(q)
			while s:
				(i, j) = q.popleft()
				s -= 1
				if j == m - 1:
					return ans
				for k in range(4):
					(x, y) = (i + d[k], j + d[3 - k])
					if x >= 0 and x < n and (y >= 0) and (y < m) and (mat[x][y] == 1):
						mat[x][y] = 2
						q.append((x, y))
			ans += 1
		return -1


from typing import List

class Solution:

	def findShortestPath(self, G: List[List[int]]) -> int:
		(R, C) = (len(G), len(G[0]))
		p0 = [(r, c) for r in range(R) for c in range(C) if G[r][c] == 0]
		for (r, c) in p0:
			if r > 0:
				G[r - 1][c] = 0
			if r < R - 1:
				G[r + 1][c] = 0
			if c > 0:
				G[r][c - 1] = 0
			if c < C - 1:
				G[r][c + 1] = 0
		ans = 0
		(q1, q2) = ([], [(r, 0) for r in range(R) if G[r][0] == 1])
		vis = set(q2)
		while q2:
			(q1, q2) = (q2, q1)
			q2.clear()
			ans += 1
			while q1:
				(r, c) = q1.pop()
				if c == C - 1:
					return ans
				for (nr, nc) in ((r + 1, c), (r - 1, c), (r, c - 1), (r, c + 1)):
					if 0 <= nr < R and 0 <= nc < C and (G[nr][nc] == 1) and ((nr, nc) not in vis):
						vis.add((nr, nc))
						q2.append((nr, nc))
		return -1


from typing import List

class Solution:

	def findShortestPath(self, G: List[List[int]]) -> int:
		(INV, R, C) = (10 ** 9, len(G), len(G[0]))
		(pre, cur) = ([INV] * R, [INV] * R)
		if R == 1:
			pre[0] = 1 if G[0][C - 1] else INV
		else:
			for i in range(1, R - 1):
				pre[i] = 1 if G[i][C - 1] and G[i + 1][C - 1] and G[i - 1][C - 1] else INV
			pre[0] = 1 if G[0][C - 1] and G[1][C - 1] else INV
			pre[R - 1] = 1 if G[R - 1][C - 1] and G[R - 2][C - 1] else INV
		for c in reversed(range(C - 1)):
			for r in range(R):
				if c > 0 and G[r][c - 1] == 0 or (r > 0 and G[r - 1][c] == 0) or (r < R - 1 and G[r + 1][c] == 0) or (G[r][c + 1] == 0) or (G[r][c] == 0):
					cur[r] = INV
				else:
					cur[r] = pre[r] + 1
			for r in range(1, R):
				if cur[r] != INV:
					cur[r] = min(cur[r], cur[r - 1] + 1)
			for r in reversed(range(R - 1)):
				if cur[r] != INV:
					cur[r] = min(cur[r], cur[r + 1] + 1)
			(pre, cur) = (cur, pre)
		mn = min(pre)
		return mn if mn < INV else -1