Shortest Path in Binary Matrix

In an N by N square grid, each cell is either empty (0) or blocked (1).

A clear path from top-left to bottom-right has a length k if and only if it is composed of cells C_1, C_2, ..., C_k such that:

• Adjacent cells C_i and C_{i+1} are connected 8-directionally (ie., they are different and share an edge or corner)
• C_1 is at location (0, 0) (ie. has value grid[0][0])
• C_k is at location (N-1, N-1) (ie. has value grid[N-1][N-1])
• If C_i is located at (r, c), then grid[r][c] is empty (ie. grid[r][c] == 0).

Return the length of the shortest such clear path from top-left to bottom-right.  If such a path does not exist, return -1.

Example:

Input:  grid={{0,1},{1,0}}
Output: 2

Approach

Java

import java.util.LinkedList;
import java.util.Queue;

public class ShortestPathInBinaryMatrix {
    public static void main(String[] args) {
        int[][] grid = { { 0, 1 }, { 1, 0 } };
        System.out.println(shortestPathBinaryMatrix(grid));
    }

    // define all 8 directions
    static int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
    static int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
    static int vis[][];
    static int dist[][];

    // function to check for
    // the cuurent cell is valid or not
    static boolean isValid(int x, int y, int[][] grid) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length)
            return false;
        if (vis[x][y] == 1 || grid[x][y] == 1)
            return false;
        return true;
    }

    // bfs function
    static void bfs(int srcx, int srcy, int[][] grid) {
        Queue<int[]> q = new LinkedList<int[]>();
        q.add(new int[] { srcx, srcy });
        dist[srcx][srcy] = 1;

        // iterate till the queue is not
        // empty
        while (!q.isEmpty()) {
            int currx = q.peek()[0];
            int curry = q.poll()[1];
            for (int i = 0; i < 8; i++) {
                if (isValid(currx + dx[i], curry + dy[i], grid)) {
                    int newx = currx + dx[i];
                    int newy = curry + dy[i];
                    q.add(new int[] { newx, newy });
                    vis[newx][newy] = 1;
                    dist[newx][newy] = dist[currx][curry] + 1;
                }
            }
        }
    }

    static int shortestPathBinaryMatrix(int[][] grid) {
        vis = new int[grid.length][grid[0].length];
        dist = new int[grid.length][grid[0].length];

        int n = grid.length;
        if (n == 0)
            return 0;
        int m = grid[0].length;
        if (grid[0][0] == 1 || grid[n - 1][m - 1] == 1)
            return -1;
        bfs(0, 0, grid);
        if (dist[n - 1][m - 1] == 0 && n != 1 && m != 1)
            return -1;
        return dist[n - 1][m - 1];
    }
}

C++

#include <bits/stdc++.h>
using namespace std;


//define all 8 directions
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};
int vis[1001][1001];
int dist[1001][1001];

//function to check for
//the cuurent cell is valid or not
bool isValid(int x,int y,vector<vector<int>> &grid)
{
        if(x<0||x>=grid.size()||y<0||y>=grid[0].size())
              return false;
         if(vis[x][y]==1||grid[x][y]==1)
               return false;
        return true;
}

//bfs function 
void bfs(int srcx,int srcy,vector<vector<int>> &grid)
{
        queue<pair<int,int>> q;
        q.push({srcx,srcy});
        dist[srcx][srcy]=1;

        //iterate till the queue is not
        //empty
        while(!q.empty())
        {
            int currx=q.front().first;
            int curry=q.front().second;
            q.pop();
            for(int i=0;i<8;i++)
            {
                if(isValid(currx+dx[i],curry+dy[i],grid))
                {
                    int newx=currx+dx[i];
                    int newy=curry+dy[i];
                    q.push({newx,newy});
                    vis[newx][newy]=1;
                    dist[newx][newy]=dist[currx][curry]+1;
                }
            }
        }
}

int shortestPathBinaryMatrix(vector<vector<int>>& grid)
{
        int n=grid.size();
        if(n==0)
              return 0;
        int m=grid[0].size();
        if(grid[0][0]==1||grid[n-1][m-1]==1)
            return -1;
        bfs(0,0,grid);
        if(dist[n-1][m-1]==0&&n!=1&&m!=1)
              return -1;
        return dist[n-1][m-1];
}

int main()
{
   vector<vector<int>> grid ={{0,1},{1,0}};
   cout<<shortestPathBinaryMatrix(grid);
   return 0;
}