Samsung Noida R&D Coding Round Question minimum distance between source and destination

There is dedicated Samsung software for coding test the question is given below:
There is one spaceship. X and Y co-odinate of source of spaceship and destination spaceship is given. There are N number of warmholes each warmhole has 5 values.
First 2 values are starting co-ordinate of warmhole and after that value no. 3 and 4 represents ending co-ordinate of warmhole and last 5th value is represents cost to pass through this warmhole. Now these warmholes are bi-direction.
Now the to go from (x1,y1) to (x2,y2) is abs(x1-x2)+abs(y1-y2).
The main problem here is to find minimum distance to reach spaceship from source to destination co-ordinate using any number of warm-hole. It is ok if you wont use any warmhole.


Solution: 

import java.util.Scanner;

class Samsung{
    static int ans=Integer.MAX_VALUE;
    static int distance(int sx,int sy,int dx,int dy)
    {
        return Math.abs(sx-dx)+Math.abs(sy-dy);
    }
    static void calCulateUtil(int mat[][],int n,int sx,int sy,int dx,int dy,int dis,boolean visited[])
    {
        ans=Math.min(ans,distance(sx,sy,dx,dy)+dis);
        for(int i=0;i<n;i++)
        {
            if(visited[i]==false)
            {
                visited[i]=true;
                int temp=distance(sx,sy,mat[i][0],mat[i][1])+dis+mat[i][4];
                calCulateUtil(mat,n,mat[i][2],mat[i][3],dx,dy,temp,visited);
                temp=distance(sx,sy,mat[i][2],mat[i][3])+dis+mat[i][4];
                 calCulateUtil(mat,n,mat[i][0],mat[i][1],dx,dy,temp,visited);
                 visited[i]=false;
            }
        }
    }
    static int calCulate(int mat[][],int n,int sx,int sy,int dx,int dy,boolean visited[])
    {
        calCulateUtil(mat,n,sx,sy,dx,dy,0,visited);
        return ans;
    }
    public static void main (String[] args) {
          Scanner sc=new Scanner(System.in);
          int t=sc.nextInt();
          while(t-->0)
          {
              int n=sc.nextInt();
              int sx=sc.nextInt();
              int sy=sc.nextInt();
              int dx=sc.nextInt();
              int dy=sc.nextInt();
              int mat[][]=new int[n][5];
              boolean visited[]=new boolean[n];
              for(int i=0;i<n;i++)
              {
                  for(int j=0;j<5;j++)
                  {
                      mat[i][j]=sc.nextInt();
                  }
              }
              System.out.println(calCulate(mat,n,sx,sy,dx,dy,visited));
          }
    }
}

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

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));
}
}