Shortest Path between source to destination in matrix

Given a Boolean 2D matrix (0-based index), find whether there is a path from (0,0) to (x,y) and if there is one path, print the minimum no of steps needed to reach it, else print -1 if the destination is not reachable. Moves are possible in only four directions i.e. up, down, left and right. The path can only be created out of a cell if its value is 1.



Solution:-

BFS traversal of matrix will give us minimum distance from source to destination in matrix.

Idea behind Solution:-  Step1:-  make a boolean matrix of same dimention and assign true every 1 and false at every 0 on the basis of given matrix.

step2:- start from source and do BFS traversal of matrix and every step increase the distance by 1.

step3:- when we reach destination then return the distance.



import java.util.Scanner;
class Point
{
    int x,y,d;
    Point(int x,int y,int d)
    {
        this.x=x;
        this.y=y;
        this.d=d;
    }
}
class Queue
{
    Point p[]=new Point[10000];
    int front=-1,end=-1;
    void add(int x,int y,int d)
    {
        if(front==-1)
            front=0;
        if(end<9999)
        {
            p[++end]=new Point(x,y,d);
        }
    }
    Point poll()
    {
        Point x=p[front++];
        return x;
    }
    boolean isEmpty()
    {
        if(front>end)
          return true;
        if(front==-1||end==-1)
          return true;
      return false;     
    }

}
class GFG {
    static int getMinValue(int mat[][],int n,int m,int sx,int sy,int dx,int dy)
    {
        boolean visited[][]=new boolean[n][m];
          for(int i=0;i<n;i++)
          {
              for(int j=0;j<m;j++)
              {
                  if(mat[i][j]==0)
                  visited[i][j]=true;
                  else
                  visited[i][j]=false;
              }
          }
          
          visited[sx][sy]=true;
          visited[dx][dy]=false;
          //Point p=new Point(sx,sy,0);
          Queue q=new Queue();
          q.add(sx,sy,0);
          while(!q.isEmpty())
          {
              Point p=q.poll();
              if(p.x==dx&&p.y==dy)
                return p.d;
            //left
              if(p.y-1>=0&&visited[p.x][p.y-1]==false)
              {
                  visited[p.x][p.y-1]=true;
                  q.add(p.x,p.y-1,p.d+1);
              }
              //right
              if(p.y+1<m&&visited[p.x][p.y+1]==false)
              {
                  visited[p.x][p.y+1]=true;
                  q.add(p.x,p.y+1,p.d+1);
              }
              //up
              if(p.x-1>=0&&visited[p.x-1][p.y]==false)
              {
                  visited[p.x-1][p.y]=true;
                  q.add(p.x-1,p.y,p.d+1);
              }
              //down
              if(p.x+1<n&&visited[p.x+1][p.y]==false)
              {
                  visited[p.x+1][p.y]=true;
                  q.add(p.x+1,p.y,p.d+1);
              }
             
          }
          return -1;
         
    }
    public static void main (String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int mat[][]=new int[n][m];
          for(int i=0;i<n;i++)
          {
              for(int j=0;j<m;j++)
              {
                  mat[i][j]=sc.nextInt();
              }
          }
        int sx=sc.nextInt();
        int sy=sc.nextInt();
        int dx=sc.nextInt();
        int dy=sc.nextInt();
        System.out.println(getMinValue(mat,n,m,sx,sy,dx,dy));
    }
}



 https://ide.geeksforgeeks.org/pqvGANXWLT