fork download
copy 
  1. import java. io.*;
  2. import java. util.*;
  3. public class Main {
  4. 	static int[] dx = {0,0,1,-1};
  5. 	static int[] dy = {1,-1,0,0};
  6. 	static int[][] time;
  7. 	static String[][] arr;
  8. 	static int h,w;
  9. 	static Queue<Node> q = new LinkedList<>();
  10. 	static boolean visited[][];
  11. 	static boolean fire_visited[][];
  12. 	static int fire_time[][];
  13. 	static Queue<Node>fire_q = new LinkedList<>();
  14. 	static boolean bl;
  15. 	static int fin_x, fin_y;
  16. 	static int ans;
  17. 	public static void main(String[] args) throws IOException {
  18. 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  19. 		int test_case = Integer.parseInt(br.readLine());
  20.  
  21. 		for(int m=0; m<test_case; m++) {
  22. 			ans=Integer.MAX_VALUE;
  23. 			fin_x = Integer.MAX_VALUE;
  24. 			fin_y = Integer.MAX_VALUE;
  25. 			bl = false;
  26. 			q.clear();
  27. 			fire_q.clear();
  28. 			String[] t = br.readLine().split(" ");
  29. 			w = Integer.parseInt(t[0]);		// 너비
  30. 			h = Integer.parseInt(t[1]);		//높이
  31. 			arr = new String[h][w];
  32. 			time = new int[h][w];
  33. 			fire_time = new int[h][w];
  34. 			fire_visited = new boolean[h][w];
  35.  
  36.  
  37. 			visited = new boolean[h][w];
  38.  
  39. 			for(int i=0; i<h; i++) {
  40. 				String[] input = br.readLine().split("");
  41. 				for(int j=0; j<w; j++) {
  42. 					arr[i][j] = input[j];
  43. 					if(arr[i][j].equals("@")) {
  44. 						q.add(new Node(i,j));  	// 시작위치를 넣어준다
  45. 						if(i==0 || j==0 || i==h-1 || j==w-1) {
  46. 							fin_x=0;
  47. 							fin_y=0;
  48. 							bl = true;					
  49. 						}
  50. 					}
  51. 					if(arr[i][j].equals("*")) {
  52. 						fire_q.add(new Node(i,j));
  53. 					}
  54. 				}
  55. 			}
  56. 			fire_bfs();
  57. 			bfs();
  58.  
  59. 			if(bl) {
  60. 				System.out.println(ans+1);
  61. 			}
  62. 			else {
  63. 				System.out.println("IMPOSSIBLE");
  64. 			}
  65. 		}
  66.  
  67. 	}
  68. 	public static void fire_bfs() {
  69. 		while(!fire_q.isEmpty()) {
  70. 			Node a = fire_q.poll();
  71. 			fire_visited[a.x][a.y] = true;
  72. 			for(int i=0; i<4; i++) {
  73. 				int x_1 = a.x+dx[i];
  74. 				int y_1 = a.y +dy[i];
  75. 				if(x_1>=0 && y_1>=0 && x_1<h && y_1<w) {
  76. 					if(!fire_visited[x_1][y_1] && !arr[x_1][y_1].equals("#")) {
  77. 						fire_visited[x_1][y_1] = true;
  78. 						fire_time[x_1][y_1] = fire_time[a.x][a.y]+1;
  79. 						fire_q.add(new Node(x_1,y_1));
  80. 					}
  81. 				}
  82. 			}
  83. 		}
  84. 	}
  85. 	public static void bfs() {
  86. 		while(!q.isEmpty()) {
  87. 			Node a = q.poll();
  88. 			visited[a.x][a.y] = true;
  89. 			for(int i=0; i<4; i++) {
  90. 				int x_1 = a.x+dx[i];
  91. 				int y_1 = a.y+dy[i];
  92. 				if(x_1>=0 && y_1>=0 && x_1<h && y_1<w) {
  93.  
  94. 					if(!visited[x_1][y_1] && arr[x_1][y_1].equals(".")) {
  95. 						if(!visited[x_1][y_1] && fire_time[x_1][y_1]>time[a.x][a.y]+1 || fire_time[x_1][y_1]==0) {
  96. 							visited[x_1][y_1] = true;
  97. 							q.add(new Node(x_1,y_1));
  98. 							time[x_1][y_1] = time[a.x][a.y]+1;
  99. 							if(x_1==0 || y_1==0 || x_1==h-1 || y_1==w-1) {
  100. 								bl = true;
  101. 								ans=Math.min(ans, time[x_1][y_1]);
  102. 							}
  103. 						}
  104. 					}
  105. 				}
  106. 			}
  107. 		}
  108. 	}
  109. }
  110. class Node{
  111. 	int x;
  112. 	int y;
  113.  
  114. 	Node(int x, int y){
  115. 		this.x= x;
  116. 		this. y= y;
  117. 	}
  118. }
Success #stdin #stdout 0.06s 33036KB
comments (?)
stdin
copy 
1
3 2
@.#
###
stdout
copy 
2
https://ideone.com/y7ZBDm
language:
Java (HotSpot 12)
created:
4 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!