Solved! Leetcode 1091. Shortest Path in Binary Matrix

source: https://leetcode.com/problems/shortest-path-in-binary-matrix/description/

Shortest Path in Binary Matrix

Description

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

class Solution {
    //8 valid directions 
    int[] xDir = new int[] {-1,-1,-1,0,0,0,1,1,1};
    int[] yDir = new int[] {-1,0,1,-1,0,1,-1,0,1};

    public int shortestPathBinaryMatrix(int[][] grid) {
        if(grid[0][0] != 0 || grid[grid.length-1][grid[0].length -1] != 0) return -1;
        Queue<int[]> queue = new LinkedList<>();
        //add the first cell to the queue as the starting location
        queue.add(new int[] {0, 0});
        //update the value of the cell to 1 to indicate that it is visited.
        grid[0][0] = 1;
        int path = Integer.MAX_VALUE;
        while(!queue.isEmpty()) {
            int[] d = queue.poll();
            //if the cell is the destination (rightmost bottom cell)
            //update the path length
            if (d[0] == grid.length -1 && d[1] == grid[0].length -1) {
                path = Math.min(path, grid[d[0]][d[1]]);
            }
            for(int i =0;i<xDir.length;i++) {
                int newRow = d[0] + xDir[i];
                int newCol = d[1] + yDir[i];
                if(isValidCell(newRow, newCol, grid)) {
                    //set the value of the cell to 1
                    grid[newRow][newCol] = grid[d[0]][d[1]] + 1;
                    queue.add(new int[] {newRow, newCol});
                }
            }
        }
        return path == Integer.MAX_VALUE ? -1 : path;

    }

    private boolean isValidCell(int i, int j, int[][] grid) {
        //a valid cell is a cell with a valid coordinates and the value of the cell is 0
        if(i<0 || i>= grid.length || j<0 || j>= grid[0].length)
            return false;
        if(grid[i][j] != 0) return false;
        return true;
    }
}

class Solution {

//8 valid directions

int[] xDir = new int[] {-1,-1,-1,0,0,0,1,1,1};

int[] yDir = new int[] {-1,0,1,-1,0,1,-1,0,1};

public int shortestPathBinaryMatrix(int[][] grid) {

if(grid[0][0] != 0 || grid[grid.length-1][grid[0].length -1] != 0) return -1;

Queue<int[]> queue = new LinkedList<>();

//add the first cell to the queue as the starting location

queue.add(new int[] {0, 0});

//update the value of the cell to 1 to indicate that it is visited.

grid[0][0] = 1;

int path = Integer.MAX_VALUE;

while(!queue.isEmpty()) {

int[] d = queue.poll();

//if the cell is the destination (rightmost bottom cell)

//update the path length

if (d[0] == grid.length -1 && d[1] == grid[0].length -1) {

path = Math.min(path, grid[d[0]][d[1]]);

}

for(int i =0;i<xDir.length;i++) {

int newRow = d[0] + xDir[i];

int newCol = d[1] + yDir[i];

if(isValidCell(newRow, newCol, grid)) {

//set the value of the cell to 1

grid[newRow][newCol] = grid[d[0]][d[1]] + 1;

queue.add(new int[] {newRow, newCol});

}

return path == Integer.MAX_VALUE ? -1 : path;

}

private boolean isValidCell(int i, int j, int[][] grid) {

//a valid cell is a cell with a valid coordinates and the value of the cell is 0

if(i<0 || i>= grid.length || j<0 || j>= grid[0].length)

return false;

if(grid[i][j] != 0) return false;

return true;

}

Rate this post

Coddicted