Sunday, 4 August 2019

Find whether there is path between two cells in matrix


Solution:-

import java.util.*;
class Point
{
    int x,y;
    Point(int x,int y)
    {
        this.x=x;
        this.y=y;
    }
}
class Queue
{
    Point p[]=new Point[10000];
    int front=-1,end=-1;
    void add(int x,int y)
    {
        if(front==-1)
            front=0;
        if(end<9999)
        {
            p[++end]=new Point(x,y);
        }
    }
    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 String check(int mat[][],int n,int m)
    {
        boolean visited[][]=new boolean[n][m];
        Point p=new Point(0,0);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(mat[i][j]==1)
                {
                    p.x=i;
                    p.y=j;
                }
                else if(mat[i][j]==0)
                 visited[i][j]=true;
                 else
                 visited[i][j]=false;
            }
        }
        Queue q=new Queue();
        q.add(p.x,p.y);
        visited[p.x][p.y]=true;
        while(!q.isEmpty())
        {
            p=q.poll();
            if(mat[p.x][p.y]==2)
             return "YES";
             //left
            if(p.y-1>=0&&visited[p.x][p.y-1]==false)
            {
                q.add(p.x,p.y-1);
                visited[p.x][p.y-1]=true;
            }
            //right
             if(p.y+1<m&&visited[p.x][p.y+1]==false)
            {
                q.add(p.x,p.y+1);
                visited[p.x][p.y+1]=true;
            }
            //bottom
             if(p.x+1<n&&visited[p.x+1][p.y]==false)
            {
                q.add(p.x+1,p.y);
                visited[p.x+1][p.y]=true;
            }
            //top
             if(p.x-1>=0&&visited[p.x-1][p.y]==false)
            {
                q.add(p.x-1,p.y);
                visited[p.x-1][p.y]=true;
            }
        }
        return "NO";
    }
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();
    }
}
System.out.println(check(mat,n,m));
}
}




No comments:

Post a Comment