fork download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.util.*;
  4.  
  5. public class Main {
  6. 	static int[] dx = {-1,1,0,0};
  7. 	static int[] dy = {0,0,-1,1};
  8. 	static int n;
  9. 	static int[][] map;
  10. 	static boolean[][] visited;
  11. 	static int[][] tmp_map;
  12. 	static int count = 0;
  13. 	static int s_x, s_y;
  14. 	static int shark_size = 2;
  15. 	static int tmp_food = 0;
  16. 	static ArrayList<dot> arr = new ArrayList<dot>();
  17. 	static int time = 0;
  18.  
  19. 	public static void main(String[] args) throws Exception{
  20. 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  21.  
  22. 		n = Integer.parseInt(br.readLine());
  23.  
  24. 		map = new int[n][n];
  25. 		tmp_map = new int[n][n];
  26. 		visited = new boolean[n][n];
  27.  
  28. 		for(int i=0; i<n; i++) {
  29. 			String[] str = br.readLine().split(" ");
  30. 			for(int j=0; j<n; j++) {
  31. 				map[i][j] = Integer.parseInt(str[j]);
  32.  
  33. 				if(map[i][j] == 9) {
  34. 					s_x = i;
  35. 					s_y = j;
  36. 				}
  37. 			}
  38. 		}
  39.  
  40. 		solve(new dot(s_x, s_y));		
  41. 		System.out.println(time);
  42.  
  43. 	}
  44.  
  45. 	static void find(dot d) {
  46. 		arr = new ArrayList<dot>();
  47. 		Queue<dot> q = new LinkedList<dot>();
  48. 		visited[d.x][d.y] = true;
  49. 		q.add(d);
  50.  
  51. 		while(!q.isEmpty()) {
  52. 			dot t = q.remove();
  53. 			int x = t.x;
  54. 			int y = t.y;
  55.  
  56. 			if(map[x][y] < shark_size && map[x][y] >= 1 && map[x][y] <=6) {
  57. 				arr.add(new dot(x,y));
  58. 			}
  59.  
  60. 			for(int i=0; i<4; i++) {
  61. 				int x1 = x + dx[i];
  62. 				int y1 = y + dy[i];
  63.  
  64. 				if(isRange(x1,y1) && !visited[x1][y1] && tmp_map[x1][y1] == 0 && map[x1][y1] <= shark_size) {
  65. 					q.add(new dot(x1,y1));
  66. 					tmp_map[x1][y1] = tmp_map[x][y] + 1;
  67. 					visited[x1][y1] = true;
  68.  
  69. 				}
  70. 			}
  71. 		}
  72.  
  73. 	}
  74.  
  75. 	static boolean isRange(int x,int y) {
  76. 		if(x>=0 && x<n && y>=0 && y<n) {
  77. 			return true;
  78. 		} else {
  79. 			return false;
  80. 		}
  81. 	}
  82.  
  83.  
  84. 	static dot whoEat() {
  85. 		ArrayList<Integer> distance = new ArrayList<Integer>();
  86. 		ArrayList<Integer> minDistanceDot_x = new ArrayList<Integer>();
  87. 		ArrayList<Integer> minDistanceDot_y = new ArrayList<Integer>();
  88.  
  89. 		//최소 거리 구하기
  90. 		for(int i=0; i<arr.size(); i++) {
  91. 			distance.add(tmp_map[arr.get(i).x][arr.get(i).y]);
  92. 		}
  93.  
  94. 		int min_distance = Collections.min(distance);
  95.  
  96. 		//최소 거리의 x,y 좌표 구하기
  97. 		for(int i=0; i<arr.size(); i++) {
  98. 			if(tmp_map[arr.get(i).x][arr.get(i).y] == min_distance) {
  99. 				minDistanceDot_x.add(arr.get(i).x);
  100. 				minDistanceDot_y.add(arr.get(i).y);
  101. 			}
  102. 		}
  103.  
  104. 		//가장 위의 x좌표 구하기
  105. 		int min_x = Collections.min(minDistanceDot_x);
  106. 		int min_y = Integer.MAX_VALUE;
  107.  
  108. 		//가장 위의 x좌표중 가장 왼쪽의 x좌표 구하기
  109. 		for(int i=0; i<minDistanceDot_x.size(); i++) {
  110. 			if(minDistanceDot_x.get(i) == min_x) {
  111. 				if(min_y > minDistanceDot_y.get(i)) {
  112. 					min_y = minDistanceDot_y.get(i);
  113. 				}
  114. 			}
  115. 		}
  116.  
  117. 		//min_y index에 있는 minDot구하기.
  118. 		dot minDot = arr.get(minDistanceDot_y.indexOf(min_y));
  119.  
  120. 		//아기상어가 먹이를 먹고 이동
  121. 		map[s_x][s_y] = 0;
  122. 		s_x = minDot.x;
  123. 		s_y = minDot.y;
  124. 		map[s_x][s_y] = 9;
  125. 		//먹이를 먹은 수 체크해서 shark_size와 같으면 shark_size 증가하고  먹은 count를 다시 0으로
  126. 		count++;
  127. 		if(count == shark_size) {
  128. 			shark_size++;
  129. 			count = 0;
  130. 		}
  131. 		//최소 거리 시간만큼 더해주기
  132. 		time += min_distance;
  133.  
  134. 		return minDot;
  135.  
  136. 	}
  137.  
  138. 	static void solve(dot d) {
  139. 		//맨 처음 d를 넣어주고 arr 사이즈 체크 (0이라면 종료)
  140. 		//아니라면 whoEat() 실행
  141. 		//whoEat()까지 실행하면 visited와 거리를 측정하는 tmp_map 초기화
  142. 		dot tmp = d;
  143. 		while(true) {
  144. 			find(tmp);
  145. 			if(arr.size()==0) {
  146. 				break;
  147. 			}
  148. 			tmp = whoEat();
  149.  
  150. 			visited = new boolean[n][n];
  151. 			tmp_map = new int[n][n];
  152.  
  153. 		}
  154. 	}
  155.  
  156. }
  157.  
  158. class dot {
  159. 	int x;
  160. 	int y;
  161.  
  162. 	public dot(int x,int y) {
  163. 		this.x = x;
  164. 		this.y = y;
  165. 	}
  166. }
Success #stdin #stdout 0.06s 32828KB
comments (?)
stdin
copy 
6
1 0 0 0 0 0
6 6 6 6 6 0
1 0 6 0 9 0
2 0 6 0 6 6
6 0 0 0 6 6
6 6 6 6 6 6
stdout
copy 
39
https://ideone.com/EFtsLD
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!