fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. /**
  5.  * Created by Shreyans on 4/30/2015 at 10:27 PM using IntelliJ IDEA (Fast IO Template)
  6.  */
  7.  
  8. //ADD PUBLIC FOR CF,TC
  9. class C
  10. {
  11.     static int r,c,s1,s2,f1,f2;//Rows, Columns, Start Coordinates, Finish Coordinates
  12.     static int[] dx={1,-1,0,0};//right, left, NA, NA
  13.     static int[] dy={0,0,1,-1};//NA, NA, bottom, top
  14.     static char[][] grid;//Main grid
  15.     public static void main(String[] args)
  16.     {
  17.         InputReader in = new InputReader(System.in);
  18.         OutputWriter out=new OutputWriter(System.out);
  19.         r=in.readInt();
  20.         c=in.readInt();
  21.         grid=new char[r][c];
  22.         for(int i=0;i<r;i++)
  23.         {
  24.             char[] s1=in.readString().toCharArray();//Reading a line of the Grid
  25.             System.arraycopy(s1,0,grid[i],0,c);//Nice inbuilt function to copy contents of an array. Also doable manually
  26.         }
  27.         s1=in.readInt()-1;
  28.         s2=in.readInt()-1;
  29.         f1=in.readInt()-1;
  30.         f2=in.readInt()-1;
  31.         if(MAZEBFS())
  32.         {
  33.            out.printLine("YES");
  34.         }
  35.         else
  36.         {
  37.             out.printLine("NO");
  38.         }
  39.         out.close();
  40.     }
  41.     private static boolean MAZEBFS()
  42.     {
  43.         if(s1==f1&&s2==f2)//case where start and end are the same
  44.         {
  45.             int[]curr={s1,s2};
  46.             for(int i=0;i<4;i++)//for each direction
  47.             {
  48.                 if((curr[0]+dx[i]>=0&&curr[0]+dx[i]<r)&&(curr[1]+dy[i]>=0&&curr[1]+dy[i]<c))
  49.                 {
  50.                     //Checked if x and y are correct. ALL IN 1 GO
  51.                     int xc=curr[0]+dx[i];//Setting current x coordinate
  52.                     int yc=curr[1]+dy[i];//Setting current y coordinate
  53.                     if(grid[xc][yc]=='E')//Cant jump on same tile so he gotta go and come back. Only possible when adjacent tiles are empty
  54.                     {
  55.                         //System.out.println(xc+" "+yc);
  56.                         return true;
  57.                     }
  58.                 }
  59.             }
  60.             return false;
  61.         }
  62.         else
  63.         {
  64.             grid [f1][f2]='G';//goal
  65.             Queue<int[]> q=new LinkedList<int[]>();
  66.             int[]start={s1,s2};//Start Coordinates
  67.             q.add(start);//Adding start to the queue since we're already visiting it
  68.             grid[s1][s2]='X';
  69.             while(q.peek()!=null)
  70.             {
  71.                 int[]curr=q.poll();//poll or remove. Same thing
  72.                 for(int i=0;i<4;i++)//for each direction
  73.                 {
  74.                     if((curr[0]+dx[i]>=0&&curr[0]+dx[i]<r)&&(curr[1]+dy[i]>=0&&curr[1]+dy[i]<c))
  75.                     {
  76.                         //Checked if x and y are correct. ALL IN 1 GO
  77.                         int xc=curr[0]+dx[i];//Setting current x coordinate
  78.                         int yc=curr[1]+dy[i];//Setting current y coordinate
  79.                         if(grid[xc][yc]=='G')//Destination found
  80.                         {
  81.                             //System.out.println(xc+" "+yc);
  82.                             return true;
  83.                         }
  84.                         else if(grid[xc][yc]=='.')//Movable. Can't return here again so setting it to 'X' now
  85.                         {
  86.                             //System.out.println(xc+" "+yc);
  87.                             grid[xc][yc]='X';//now BLOCKED
  88.                             int[]temp={xc,yc};
  89.                             q.add(temp);//Adding current coordinates to the queue
  90.                         }
  91.                     }
  92.                 }
  93.             }
  94.             return false;//Will return false if no route possible
  95.         }
  96.     }
  97.     //FAST IO
  98.     private static class InputReader
  99.     {
  100.         private InputStream stream;
  101.         private byte[] buf = new byte[1024];
  102.         private int curChar;
  103.         private int numChars;
  104.         private SpaceCharFilter filter;
  105.  
  106.         public InputReader(InputStream stream)
  107.         {
  108.             this.stream = stream;
  109.         }
  110.  
  111.         public int read()
  112.         {
  113.             if (numChars == -1)
  114.                 throw new InputMismatchException();
  115.             if (curChar >= numChars)
  116.             {
  117.                 curChar = 0;
  118.                 try
  119.                 {
  120.                     numChars = stream.read(buf);
  121.                 } catch (IOException e)
  122.                 {
  123.                     throw new InputMismatchException();
  124.                 }
  125.                 if (numChars <= 0)
  126.                     return -1;
  127.             }
  128.             return buf[curChar++];
  129.         }
  130.  
  131.         public int readInt()
  132.         {
  133.             int c = read();
  134.             while (isSpaceChar(c))
  135.                 c = read();
  136.             int sgn = 1;
  137.             if (c == '-')
  138.             {
  139.                 sgn = -1;
  140.                 c = read();
  141.             }
  142.             int res = 0;
  143.             do
  144.             {
  145.                 if (c < '0' || c > '9')
  146.                     throw new InputMismatchException();
  147.                 res *= 10;
  148.                 res += c - '0';
  149.                 c = read();
  150.             } while (!isSpaceChar(c));
  151.             return res * sgn;
  152.         }
  153.  
  154.         public String readString()
  155.         {
  156.             int c = read();
  157.             while (isSpaceChar(c))
  158.                 c = read();
  159.             StringBuilder res = new StringBuilder();
  160.             do
  161.             {
  162.                 res.appendCodePoint(c);
  163.                 c = read();
  164.             } while (!isSpaceChar(c));
  165.             return res.toString();
  166.         }
  167.  
  168.         public double readDouble()
  169.         {
  170.             int c = read();
  171.             while (isSpaceChar(c))
  172.                 c = read();
  173.             int sgn = 1;
  174.             if (c == '-')
  175.             {
  176.                 sgn = -1;
  177.                 c = read();
  178.             }
  179.             double res = 0;
  180.             while (!isSpaceChar(c) && c != '.')
  181.             {
  182.                 if (c == 'e' || c == 'E')
  183.                     return res * Math.pow(10, readInt());
  184.                 if (c < '0' || c > '9')
  185.                     throw new InputMismatchException();
  186.                 res *= 10;
  187.                 res += c - '0';
  188.                 c = read();
  189.             }
  190.             if (c == '.')
  191.             {
  192.                 c = read();
  193.                 double m = 1;
  194.                 while (!isSpaceChar(c))
  195.                 {
  196.                     if (c == 'e' || c == 'E')
  197.                         return res * Math.pow(10, readInt());
  198.                     if (c < '0' || c > '9')
  199.                         throw new InputMismatchException();
  200.                     m /= 10;
  201.                     res += (c - '0') * m;
  202.                     c = read();
  203.                 }
  204.             }
  205.             return res * sgn;
  206.         }
  207.  
  208.         public long readLong()
  209.         {
  210.             int c = read();
  211.             while (isSpaceChar(c))
  212.                 c = read();
  213.             int sgn = 1;
  214.             if (c == '-')
  215.             {
  216.                 sgn = -1;
  217.                 c = read();
  218.             }
  219.             long res = 0;
  220.             do
  221.             {
  222.                 if (c < '0' || c > '9')
  223.                     throw new InputMismatchException();
  224.                 res *= 10;
  225.                 res += c - '0';
  226.                 c = read();
  227.             } while (!isSpaceChar(c));
  228.             return res * sgn;
  229.         }
  230.  
  231.         public boolean isSpaceChar(int c)
  232.         {
  233.             if (filter != null)
  234.                 return filter.isSpaceChar(c);
  235.             return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  236.         }
  237.  
  238.         public String next()
  239.         {
  240.             return readString();
  241.         }
  242.  
  243.         public interface SpaceCharFilter
  244.         {
  245.             public boolean isSpaceChar(int ch);
  246.         }
  247.     }
  248.  
  249.     private static class OutputWriter
  250.     {
  251.         private final PrintWriter writer;
  252.  
  253.         public OutputWriter(OutputStream outputStream)
  254.         {
  255.             writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  256.         }
  257.  
  258.         public OutputWriter(Writer writer)
  259.         {
  260.             this.writer = new PrintWriter(writer);
  261.         }
  262.  
  263.         public void print(Object... objects)
  264.         {
  265.             for (int i = 0; i < objects.length; i++)
  266.             {
  267.                 if (i != 0)
  268.                     writer.print(' ');
  269.                 writer.print(objects[i]);
  270.             }
  271.         }
  272.  
  273.         public void printLine(Object... objects)
  274.         {
  275.             print(objects);
  276.             writer.println();
  277.         }
  278.  
  279.         public void close()
  280.         {
  281.             writer.close();
  282.         }
  283.  
  284.         public void flush()
  285.         {
  286.             writer.flush();
  287.         }
  288.     }
  289. }
Success #stdin #stdout 0.1s 320320KB
comments (?)
stdin
copy 
4 7
..X.XX.
.XX..X.
X...X..
X......
2 2
1 6
stdout
copy 
YES
https://ideone.com/JS4OAU
language:
Java (HotSpot 12)
created:
8 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!