fork download
copy 
  1.  
  2. import java.awt.Point;
  3. import java.io.BufferedReader;
  4. import java.io.FileNotFoundException;
  5. import java.io.FileReader;
  6. import java.io.FileWriter;
  7. import java.io.IOException;
  8. import java.io.InputStream;
  9. import java.io.InputStreamReader;
  10. import java.io.PrintWriter;
  11. import java.lang.reflect.Array;
  12. import java.math.BigInteger;
  13. import java.sql.PreparedStatement;
  14. import java.text.Collator;
  15. import java.util.ArrayList;
  16. import java.util.Arrays;
  17. import java.util.Collections;
  18. import java.util.Comparator;
  19. import java.util.HashMap;
  20. import java.util.LinkedList;
  21. import java.util.Queue;
  22. import java.util.Scanner;
  23. import java.util.Stack;
  24. import java.util.StringTokenizer;
  25.  
  26.  
  27.  
  28.  
  29.  
  30.  class TestClass {
  31.  
  32. static int[] dist ;	
  33. static int[][][] vis;
  34. static ArrayList<Integer>[] resu;
  35. static char[][] graph;
  36. static int max;
  37. static int min;
  38. static int[][][] dp;
  39. static int zz;
  40. static int zzz;
  41. static boolean fin;
  42.  
  43.  
  44. static class facebook{
  45.  
  46. 	int x ;
  47. 	int y ;
  48. 	int d;
  49. 	int moves;
  50.  
  51. 	public  facebook(int x , int y , int d , int moves){
  52. 		   this.x = x;
  53. 		   this.y = y;
  54. 		   this.d =d;
  55. 		   this.moves = moves;
  56. 	}
  57.  
  58. }
  59.  
  60. public static boolean check_s(int i , int j){
  61.  
  62. 	if(graph[i][j]==0 ||graph[i][j]==1 || graph[i][j]==2 || graph[i][j]==3 ) return true;
  63.  
  64. 	return false;
  65. }
  66.  
  67.  
  68. public static void check(int x , int y , int moves){
  69.  
  70.         if(moves==0){
  71.         	x--;
  72.           while(x>=0){
  73.  
  74.         	 if(graph[x][y]== '#' || check_s(x, y)) break;
  75.         	 else{
  76.         		  dp[x][y][0] = Integer.MAX_VALUE;
  77.         		  x--;
  78.         	 }
  79.           }
  80.         }
  81.         else if(moves==1){
  82.         	   y++;
  83.         	   while(y<graph[0].length){
  84.         			 if(graph[x][y]== '#' || check_s(x, y)) break;
  85.         			 else{
  86.         				 dp[x][y][1] = Integer.MAX_VALUE;
  87.         				 y++;
  88.         			 }
  89.         	   }
  90.  
  91.         }
  92.         else if(moves==2){
  93.         	x++;
  94.         	while(x<graph.length){
  95.         		 if(graph[x][y]== '#' || check_s(x, y)) break;
  96.         		 else{
  97.         			 dp[x][y][2] =Integer.MAX_VALUE;
  98.         			 x++;
  99.         		 }
  100.         	}
  101.         }
  102.         else if(moves==3){
  103.         	y--;
  104.         	while(y>=0){
  105.         		 if(graph[x][y]== '#' || check_s(x, y)) break;
  106.         		 else{
  107.         			 dp[x][y][3] =Integer.MAX_VALUE;
  108.         			 y--;
  109.         		 }
  110.         	}
  111.         }
  112.  
  113.  
  114. }
  115. public static int visitedcheck(int i , int j , int moves){
  116.  
  117. 	if(zz==-1) return 0;
  118.  
  119. 	int xx = graph[zz][zzz]+moves;
  120. 	return (xx%4);
  121. }
  122.  
  123. public static boolean iscorrect(int i , int j , int moves){
  124. 	int temp;
  125. 	  temp=i-1;
  126. 	   while(temp>=0){
  127.  
  128. 		   if(graph[temp][j]== '#') break;
  129. 		   else if(check_s(temp, j)){
  130.  
  131. 			   int xx = (graph[temp][j]+ moves)%4;
  132. 			   if(dp[i][j][xx]==Integer.MAX_VALUE) return false;
  133. 			   else break;
  134. 		   }
  135. 		     temp--;
  136.  
  137.  
  138. 	   }
  139.  
  140. 	   temp = i+1;
  141. 	   while(temp<graph.length){
  142.  
  143. 		   if(graph[temp][j]== '#') break;
  144. 		   else if(check_s(temp, j)){
  145.  
  146. 			   int xx = (graph[temp][j]+ moves)%4;
  147. 			   if(dp[i][j][xx]==Integer.MAX_VALUE) return false;
  148. 			   else break;
  149. 		   }
  150. 		     temp++;
  151. 	   }
  152.  
  153. 	   temp = j+1;
  154. 	   while(temp<graph[0].length){
  155.  
  156. 		   if(graph[i][temp]== '#') break;
  157. 		   else if(check_s(i, temp)){
  158.  
  159. 			   int xx = (graph[i][temp]+ moves)%4;
  160.  
  161. 			   if(dp[i][j][xx]==Integer.MAX_VALUE) return false;
  162. 			   else break;
  163. 		   }
  164. 		     temp++;
  165. 	   }
  166. 	   temp = j-1;
  167. 	   while(temp>=0){
  168. 		   if(graph[i][temp]== '#') break;
  169. 		   else if(check_s(i, temp)){
  170.  
  171. 			   int xx = (graph[i][temp]+ moves)%4;
  172. 			   if(dp[i][j][xx]==Integer.MAX_VALUE) return false;
  173. 			   else break;
  174. 		   }
  175. 		     temp--;
  176. 	   }
  177.  
  178.  
  179.  
  180. 	 return true;
  181. }
  182.  
  183. public static void findanswer(int current_x , int current_y , int final_x, int final_y){
  184.  
  185.  
  186. 	  int[] x = {1,-1,0,0};
  187. 	  int[] y = {0,0,1,-1};
  188. 	 vis[current_x][current_y][visitedcheck(current_x, current_y, 0)] =1;
  189. 	  facebook obj = new facebook(current_x, current_y, 0, 0);
  190. 	  LinkedList<facebook> Q = new LinkedList<TestClass.facebook>();
  191. 	  Q.add(obj);
  192.  
  193. 	  while(!Q.isEmpty()){
  194.  
  195. 		  int xx =  Q.peek().x;
  196. 		  int yy = Q.peek().y;
  197. 		  int d = Q.peek().d;
  198. 		  int mov = Q.peek().moves;
  199. 		  Q.pop();
  200.  
  201. 		  for(int i=0;i<4;i++){
  202.  
  203. 			  int dx = xx + x[i];
  204. 			  int dy = yy + y[i];
  205. 			  int moves = mov+1;
  206. 			  int dist = d+1;
  207. 	if(dx>=0 && dy>=0 && dx<graph.length && dy<graph[0].length && graph[dx][dy]!='#' &&!check_s(dx, dy) && vis[dx][dy][visitedcheck(dx, dy, moves)]!=1){
  208.  
  209. 		             if(iscorrect(dx, dy, moves)){
  210. 		            	// System.out.println(dx+" "+dy+" "+moves);
  211. 		            	 if(dx==final_x && dy== final_y){
  212. 		            		 if(max>dist) max=dist;
  213. 		            		// System.out.println(dist);
  214. 		            		 //vis[dx][dy][visitedcheck(dx, dy, moves)]=1;
  215. 		            	 }else{
  216. 		            	 obj = new facebook(dx, dy, d+1, moves);
  217. 		            	 Q.add(obj);
  218. 		            	 vis[dx][dy][visitedcheck(dx, dy, moves)]=1;
  219.  
  220. 		            	 }
  221.  
  222. 		             }
  223. 	}
  224. 		  }
  225.  
  226. 	  }
  227.  
  228.  
  229.  
  230.  
  231.  
  232.  
  233.  
  234.  
  235. }
  236.  
  237.  
  238. public static void main(String args[] ) throws IOException  {
  239.  
  240.  
  241. Scanner in = new Scanner(new InputStreamReader(System.in));
  242. int t = in.nextInt();
  243. for(int i=1;i<=t;i++){
  244. 	int n =in.nextInt();
  245. 	int m = in.nextInt();
  246. 	graph = new char[n][m];
  247. 	dp = new int[n][m][4];
  248. 	vis = new int[n][m][4];
  249. 	int sourcex = 0 , sourcey=0;
  250. 	int distx=0 , disty=0;
  251. 	zz= -1; zzz=-1;
  252.  
  253. 	for(int j=0;j<n;j++)
  254. 	{	
  255. 		graph[j] =  in.next().toCharArray();
  256. 		for(int k=0;k<m;k++)
  257. 		{
  258. 			if(graph[j][k]=='S'){
  259. 				sourcex = j;
  260. 				sourcey =k;
  261. 			}
  262.  
  263. 			if(graph[j][k] == 'G')
  264. 			{
  265. 				 distx=j;
  266. 				 disty=k;
  267. 			}
  268. 			if(graph[j][k]=='<') {graph[j][k]=3;zz=j; zzz=k; }
  269. 			if(graph[j][k]=='>') {graph[j][k]=1;zz=j; zzz=k;}
  270. 			if(graph[j][k]=='^') {graph[j][k]=0; zz=j; zzz=k;}
  271. 			if(graph[j][k]=='v') {graph[j][k]=2; zz=j; zzz=k;}
  272. 		}
  273.  
  274.  
  275. 	}
  276. 	for(int j=0;j<n;j++)
  277. 		for(int k=0;k<m;k++){
  278.  
  279. 			if(check_s(j, k)){
  280.  
  281. 			for(int mm=0;mm<4;mm++)
  282. 			  check(j, k, mm);
  283.  
  284. 			}
  285. 		}
  286. 	max =Integer.MAX_VALUE;
  287. 	findanswer(sourcex, sourcey, distx, disty);
  288.  
  289.     if(max!=Integer.MAX_VALUE)
  290. 	System.out.println("Case #"+i+": "+max);
  291.     else
  292.     	System.out.println("Case #"+i+": impossible");
  293.     //pw.flush();
  294. 	//System.out.println(iscorrect(1, 2, 2) +" " +dp[1][2][2]);
  295.  
  296.  
  297.  
  298.  
  299.  
  300. }
  301.  
  302.  
  303.  
  304. }
  305.  }
  306.  
Success #stdin #stdout 0.11s 380672KB
comments (?)
stdin
copy 
5
2 5
##^##
S...G
2 5
##v##
S...G
1 5
S..G<
1 6
S...G<
5 5
S....
.....
.>v..
.^<..
....G
stdout
copy 
Case #1: 6
Case #2: 4
Case #3: 3
Case #4: impossible
Case #5: 8
https://ideone.com/1Y0Unj
language:
Java (12.0.1)
created:
10 years ago
visibility:
public

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!