fork download
  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
stdin
4 7
..X.XX.
.XX..X.
X...X..
X......
2 2
1 6
stdout
YES