fork(2) download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.util.ArrayList;
  4. import java.util.LinkedList;
  5. import java.util.Queue;
  6. import java.util.StringTokenizer;
  7.  
  8. public class Main{
  9. 	private static boolean [][] isRed;        // 이동이 가능하면 false or true
  10. 	private static final int[][] DIRECTIONS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
  11. 	private static final int ROW = 0;
  12. 	private static final int COL = 1;
  13. 	private static final String SPACE = " ";
  14.  
  15. 	private static class Point{
  16. 		int row;
  17. 		int col;
  18.  
  19. 		public Point(int row, int col) {
  20. 			this.row = row;
  21. 			this.col = col;
  22. 		}
  23. 	}
  24.  
  25. 	public static void main(String[] args) throws Exception{
  26. 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  27. 		StringTokenizer st = new StringTokenizer(br.readLine());
  28. 		int M = Integer.parseInt(st.nextToken());
  29. 		int N = Integer.parseInt(st.nextToken());
  30. 		int V = Integer.parseInt(st.nextToken());
  31.  
  32. 		st = new StringTokenizer(br.readLine());
  33. 		Point s = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
  34.  
  35. 		int[][] map = new int[M + 1][N + 1];
  36.  
  37. 		for(int i = 1; i < M + 1; i++) {
  38. 			st = new StringTokenizer(br.readLine());
  39. 			for(int j = 1; j < N + 1; j++) {
  40. 				map[i][j] = Integer.parseInt(st.nextToken());
  41. 			}
  42. 		}
  43.  
  44. 		ArrayList<Point>[] volca = new ArrayList[201];
  45. 		for(int i = 0; i < 201; i++){
  46. 			volca[i] = new ArrayList<>();
  47. 		}
  48.  
  49. 		isRed = new boolean[M + 1][N + 1];
  50. 		for(int i = 0; i < V; i++) {
  51. 			st = new StringTokenizer(br.readLine());
  52. 			int row = Integer.parseInt(st.nextToken());
  53. 			int col = Integer.parseInt(st.nextToken());
  54. 			int timer = Integer.parseInt(st.nextToken());
  55.  
  56. 			volca[timer].add(new Point(row, col));    // 인접 리스트에 화산 폭발 시간과 그 화산의 위치를 저장합니다.
  57. 			isRed[row][col] = true;                // 화산이 존재하는 지역은 이미 이동 불가
  58. 		}
  59.  
  60. 		System.out.println(bfs(M, N, V, map, volca, s));
  61. 	}
  62.  
  63. 	private static StringBuilder bfs(int n, int m, int v, int[][] arr, ArrayList<Point>[] hole, Point start) {
  64. 		StringBuilder sb = new StringBuilder();
  65. 		int[][] isVisited = new int[n + 1][m + 1];
  66. 		int max = arr[start.row][start.col], minTime = 0;
  67.  
  68. 		Queue<Point> q = new LinkedList<>();
  69. 		q.offer(new Point(start.row, start.col));
  70. 		isVisited[start.row][start.col] = 1;     // 현 위치의 값 및 방문 여부를 저장합니다. 실제 시간: isVisited[row][col] - 1
  71.  
  72. 		while(!q.isEmpty()) {
  73. 			Point current = q.poll();
  74.             // 현재 시간에 맞춰 메소드를 호출하여 화산 쇄설류를 덮어줍니다.
  75. 			if(isVisited[current.row][current.col] < 201) covering(n, m, v, hole, isVisited[current.row][current.col]);
  76.  
  77. 			for(final int[] DIRECTION: DIRECTIONS) {
  78. 				int nextRow = current.row + DIRECTION[ROW];
  79. 				int nextCol = current.col + DIRECTION[COL];
  80.  
  81. 				if(nextRow < 1 || nextRow > n || nextCol < 1 || nextCol > m) continue;
  82. 				if(isVisited[nextRow][nextCol] != 0 || isRed[nextRow][nextCol]) continue;    // 이미 방문했거나 쇄설류가 덮친 경우
  83. 				isVisited[nextRow][nextCol] = isVisited[current.row][current.col] + 1;
  84.  
  85. 				if(arr[nextRow][nextCol] > max) max = arr[nextRow][nextCol];		// 이동할 수 있는 지역 중 최대 높이		
  86. 				q.offer(new Point(nextRow, nextCol));
  87. 			}
  88. 		}
  89.  
  90. 		minTime = getMinTime(n, m, arr, isVisited, max);
  91.  
  92. 		sb.append(max).append(SPACE).append(minTime == Integer.MAX_VALUE ? 0 : minTime);
  93. 		return sb;
  94. 	}
  95.  
  96. 	private static int getMinTime(int n, int m, int[][] arr, int[][] visit, int maxPos) {
  97. 		int min = Integer.MAX_VALUE;
  98.  
  99. 		for(int i = 1; i < n + 1; i++) {
  100. 			for(int j = 1; j < m + 1; j++) {
  101. 				if(arr[i][j] == maxPos) {        // 최대 높이 값을 갖는 행과 열의 값을 통해 최소 시간을 찾습니다.
  102. 					if(visit[i][j] - 1 < min) min = visit[i][j] - 1;
  103. 				}
  104. 			}
  105. 		}
  106.  
  107. 		return min;
  108. 	}
  109.  
  110. 	private static boolean isCovered(int holeRow, int holeCol, int row, int col, int time) {
  111. 		return time >= Math.abs(holeRow - row) + Math.abs(holeCol - col) ? true: false;
  112. 	}
  113.  
  114. 	private static void covering(int n, int m, int v, ArrayList<Point>[] hole, int timer) {
  115. 		for(int t = 0; t < timer; t++) {            // timer는 현재까지 경과된 시간입니다. 즉 isVisited의 배열값입니다.
  116. 			for(Point pair: hole[t]) {              // t시간에 폭발한 화산이 있다면          
  117. 				for(int row = 1; row < n + 1; row++) {
  118. 					for(int col = 1; col < m + 1; col++) {
  119. 						if(isRed[row][col]) continue;        // 이미 화산이 덮은 곳은 무시합니다.
  120.                         // 현재까지 경과시간(timer, isVisited) - 화산이 폭발한 시간(t) 값으로 문제의 조건대로 계산합니다.
  121.                         // 현재까지 경과시간(timer, isVisited) - 화산이 폭발한 시간(t) : 문제 설명에서 주어진 'δ' 라고 생각했습니다.
  122. 						isRed[row][col] = isCovered(row, col, pair.row, pair.col, timer - t);
  123. 					}
  124. 				}
  125. 			}
  126. 		}
  127. 	}
  128. }
  129.  
Success #stdin #stdout 0.04s 2184192KB
comments (?)
stdin
copy 
3 3 6
1 1
1 2 2
3 3 3
3 3 3
2 1 5
2 2 5
2 3 5
3 1 0
3 2 0
3 3 0
stdout
copy 
2 -1
https://ideone.com/REYmGB
language:
Java (HotSpot 12)
created:
5 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!