fork(5) download
copy 
  1. import java.util.*;
  2.  
  3. /**
  4.  * Created by Shreyans on 4/30/2015 at 10:27 PM using IntelliJ IDEA
  5.  */
  6.  
  7. class MAZE
  8. {
  9.     static int r,c,s1,s2,f1,f2;//Rows, Columns, Start Coordinates, Finish Coordinates
  10.     static int[] dx={1,-1,0,0};//right, left, NA, NA
  11.     static int[] dy={0,0,1,-1};//NA, NA, bottom, top
  12.     static char[][] grid;//Main grid
  13.     public static void main(String[] args)
  14.     {
  15.         Scanner sc=new Scanner(System.in);//I suggest using faster IO if you have performance concerns. I did. Scanner is readable hence the choice
  16.         r=sc.nextInt();
  17.         c=sc.nextInt();
  18.         grid=new char[r][c];
  19.         for(int i=0;i<r;i++)
  20.         {
  21.             char[] s1=sc.next().toCharArray();//Reading a line of the Grid
  22.             System.arraycopy(s1,0,grid[i],0,c);//Nice inbuilt function to copy contents of an array. Also doable manually
  23.         }
  24.         s1=sc.nextInt()-1;
  25.         s2=sc.nextInt()-1;
  26.         f1=sc.nextInt()-1;
  27.         f2=sc.nextInt()-1;
  28.         if(MAZEBFS())
  29.         {
  30.             System.out.println("PATH EXISTS");
  31.         }
  32.         else
  33.         {
  34.             System.out.println("PATH DOES NOT EXIST");
  35.         }
  36.     }
  37.     private static boolean MAZEBFS()
  38.     {
  39.         if(s1==f1&&s2==f2)
  40.         {
  41.             return true;//He's already there
  42.         }
  43.         else
  44.         {
  45.             grid [f1][f2]='G';//finish
  46.             Queue<int[]> q=new LinkedList<int[]>();
  47.             int[]start={s1,s2};//Start Coordinates
  48.             q.add(start);//Adding start to the queue since we're already visiting it
  49.             grid[s1][s2]='B';
  50.             while(q.peek()!=null)
  51.             {
  52.                 int[]curr=q.poll();//poll or remove. Same thing
  53.                 for(int i=0;i<4;i++)//for each direction
  54.                 {
  55.                     if((curr[0]+dx[i]>=0&&curr[0]+dx[i]<r)&&(curr[1]+dy[i]>=0&&curr[1]+dy[i]<c))
  56.                     {
  57.                         //Checked if x and y are correct. ALL IN 1 GO
  58.                         int xc=curr[0]+dx[i];//Setting current x coordinate
  59.                         int yc=curr[1]+dy[i];//Setting current y coordinate
  60.                         if(grid[xc][yc]=='G')//Destination found
  61.                         {
  62.                             //System.out.println(xc+" "+yc);
  63.                             return true;
  64.                         }
  65.                         else if(grid[xc][yc]=='E')//Movable. Can't return here again so setting it to 'B' now
  66.                         {
  67.                             //System.out.println(xc+" "+yc);
  68.                             grid[xc][yc]='B';//now BLOCKED
  69.                             int[]temp={xc,yc};
  70.                             q.add(temp);//Adding current coordinates to the queue
  71.                         }
  72.                     }
  73.                 }
  74.             }
  75.             return false;//Will return false if no route possible
  76.         }
  77.     }
  78. }
Success #stdin #stdout 0.13s 321088KB
comments (?)
stdin
copy 
4 4
SEEB
EBEE
BBBE
GEEE
1 1
1 4
stdout
copy 
PATH EXISTS
https://ideone.com/jiZKzn
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!