1091. Shortest Path in Binary Matrix

Medium

---

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

• All the visited cells of the path are 0.

• All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

Example 1:

Input: grid = [[0,1],[1,0]]
Output: 2

Example 2:

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4

Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1

Constraints:

• n == grid.length

• n == grid[i].length

• 1 <= n <= 100

• grid[i][j] is 0 or 1

Solution 1 : Little modification from solution 2 ( who reaches first at [n-1][n-1] is the shortest length

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        self.rows = len(grid)
        self.cols = len(grid[0])
        if self.rows > 0 and self.cols > 0 and (grid[0][0] != 0 or grid[self.rows-1][self.cols-1]!=0):
            return -1
        self.visited = set()
        q = []
        q.append([0,0,1]) # index 0,0 with distance 1
        while q:
            row, col , dis = q.pop(0)
            if row == self.rows-1 and col == self.cols - 1:
                return dis
            for x,y in [(0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1), (1,0), (1,1)]:
                if self.isValid(row+x, col+y) and grid[row+x][col+y] == 0 :
                    self.visited.add((row+x, col+y))
                    q.append([row+x, col+y, dis+1])
        return -1
    def isValid(self, row, col):
        if 0 <= row < self.rows and 0 <= col < self.cols and (row, col) not in self.visited:
            return True
        return False

Solution 2

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        self.rows = len(grid)
        self.cols = len(grid[0])
        if self.rows > 0 and self.cols > 0 and (grid[0][0] != 0 or grid[self.rows-1][self.cols-1]!=0):
            return -1
        self.visited = set()
        q = []
        distance = float('inf')
        q.append([0,0,1]) # index 0,0 with distance 1
        while q:
            row, col , dis = q.pop(0)
            if row == self.rows-1 and col == self.cols - 1:
                distance = min(distance, dis)
            for x,y in [(0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1), (1,0), (1,1)]:
                if self.isValid(row+x, col+y) and grid[row+x][col+y] == 0 :
                    self.visited.add((row+x, col+y))
                    q.append([row+x, col+y, dis+1])
        return -1 if distance == float("inf") else distance
    def isValid(self, row, col):
        if 0 <= row < self.rows and 0 <= col < self.cols and (row, col) not in self.visited:
            return True
        return False

Solution 3

class Solution:
    def __init__(self):
        # This is very common thing that can be used for all-direction moving
        self.directions=[(1,0),(-1,0),(0,1),(0,-1),(-1,-1),(-1,1),(1,1),(1,-1)]
        
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        # If [0,0] is 1 or bottom-right is 1 then return -1
        # because there will be no path
        row = len(grid)
        col = len(grid[0])
        if grid[0][0] == 1 or grid[-1][-1] == 1:
            return -1
        visited = [[-1 for j in range(col)] for i in range(row)]
        # [Row Index, Col Index, Moves]
        q = deque()
        q.append((0,0,1))
        visited[0][0] = 0
        while q:
            r,c,m = q.popleft()
            if r == (row-1) and c == (col-1):
                return m
            for dr,dc in self.directions:
                newR = r+dr
                newC = c+dc
                if self.isPathValid(grid, visited, newR, newC):
                    visited[newR][newC] = 0
                    q.append((newR,newC,m+1))
        return -1
            
    def isPathValid(self,grid, visited, row,col):
        if 0 <= row <= len(grid)-1 and 0 <= col <= len(grid[0])-1 and visited[row][col] == -1 and grid[row][col] == 0:
            return True
        return False