[백준] 23289. 온풍기 안녕!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	static int R, C, K, W;
	static int[][] map;
	static ArrayList[][] wall;
//	dir = {{0,0}, {0,1}, {0,-1},{-1,0},{1,0}};
	static int[][][] dir = { {{0,0},{0,0},{0,0}},
						     {{-1,1},{0,1},{1,1}},
						     {{-1,-1},{0,-1},{1,-1}},
						     {{-1,-1},{-1,0},{-1,1}},
						     {{1,-1},{1,0},{1,1}}
							};
	static boolean[][] visited;
	static ArrayList<Heater> heaters = new ArrayList(), calc = new ArrayList();
	
	static class Heater {
		int x;
		int y;
		int d;
		
		Heater(int x, int y, int d) {
			this.x=x;
			this.y=y;
			this.d=d;
		}
	}

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		map = new int[R][C];
		wall = new ArrayList[R][C];
		
		for(int i=0; i<R; i++) {
			for(int j=0; j<C; j++) {
				wall[i][j] = new ArrayList();
			}
		}
		
		for(int i=0; i<R; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<C; j++) {
				
				/*
					0: 빈 칸
					1: 방향이 오른쪽인 온풍기가 있음
					2: 방향이 왼쪽인 온풍기가 있음
					3: 방향이 위인 온풍기가 있음
					4: 방향이 아래인 온풍기가 있음
					5: 온도를 조사해야 하는 칸  
				 */
				int v = Integer.parseInt(st.nextToken());
				
				if(v != 0 && v != 5) {
					heaters.add(new Heater(i, j, v));
				}
				if(v == 5) {
					calc.add(new Heater(i, j, v));
				}
				
			}
		}
		
		st = new StringTokenizer(br.readLine());
		W = Integer.parseInt(st.nextToken());
		
		for(int i=0; i<W; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int t = Integer.parseInt(st.nextToken());
			
			wall[x-1][y-1].add(t); 
		}
		
		int chocolate;
		
		for(chocolate=1; chocolate<=100; chocolate++) {
			// 1. 집에 있는 모든 온풍기에서 바람이 한 번 나옴
			wind();
			
	//		print(map);
			
			// 2. 온도가 조절됨
			adjust();
			
	//		print(map);
			
			// 3. 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소
			decrease();
			
			// 4. 초콜릿을 하나 먹는다.
			
			// 5. 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사. 모든 칸의 온도가 K이상이면 테스트를 중단하고, 아니면 1부터 다시 시작한다.
			if(inspect()) {
				break;
			}
		}
		
//		print(map);
		
		System.out.println(chocolate);
	}
	
	public static boolean inspect() {
		for(int i=0; i<calc.size(); i++) {
			Heater h = calc.get(i);
			
			if(map[h.x][h.y] < K) return false; 
		}
		
		return true;
	}
	
	public static void wind() {
		
		for(int i=0; i<heaters.size(); i++) {
			Heater h = heaters.get(i);
			
			visited = new boolean[R][C];
			
//			visited[h.x][h.y] = true;
			
			dfs(h.x, h.y, h.d, 5);
		}
	}
	
	public static void adjust() {
		visited = new boolean[R][C];
		
		int[][] temp_map = new int[R][C];
		
		for(int i=0; i<map.length; i++) {
			for(int j=0; j<map[i].length; j++) {
				
				visited[i][j] = true;
				
				for(int k=1; k<=4; k++) {
					int nx = i + dir[k][1][0];
					int ny = j + dir[k][1][1];
					
					if(isInside(nx, ny) && !visited[nx][ny]) {
						
						if(!isWall(nx, ny, k, 1)) continue;
						
						int result = Math.abs(map[i][j] - map[nx][ny])/4;
						
						if(map[i][j] > map[nx][ny]) {
							temp_map[i][j] -= result;
							temp_map[nx][ny] += result;
						} else {
							temp_map[nx][ny] -= result;
							temp_map[i][j] += result;
						}
					}
				}
			}
		}
		
		for(int i=0; i<map.length; i++) {
			for(int j=0; j<map[i].length; j++) {
				map[i][j] += temp_map[i][j];
			}
		}
	}
	
	public static void decrease() {
		for(int i=0; i<R; i++) {
			if(map[i][0] > 0) map[i][0]--;
			if(map[i][C-1] > 0) map[i][C-1]--;
		}
		for(int j=1; j<C-1; j++) {
			if(map[0][j] > 0) map[0][j]--;
			if(map[R-1][j] > 0) map[R-1][j]--;
		}
	}
	
	public static void dfs(int x, int y, int d, int v) {
		if(v <= 0) {
			return;
		}
		
		if(v == 5) {
			int nx = x + dir[d][1][0];
			int ny = y + dir[d][1][1];
			
			if(isInside(nx, ny) && !visited[nx][ny]) {
				
				if(!isWall(nx, ny, d, 1)) return;
				
				map[nx][ny] += v;
				visited[nx][ny] = true;
				dfs(nx, ny, d, v-1);
			}
		} else {
			for(int i=0; i<3; i++) {
				int nx = x + dir[d][i][0];
				int ny = y + dir[d][i][1];
				
				if(isInside(nx, ny) && !visited[nx][ny]) {
					
					if(!isWall(nx, ny, d, i)) continue;
					
					map[nx][ny] += v;
					visited[nx][ny] = true;
					dfs(nx, ny, d, v-1);
				}
			}
		}
		
	}
	
	public static boolean isWall(int x, int y, int d, int i) {
		/*
		0: 빈 칸
		1: 방향이 오른쪽인 온풍기가 있음
		2: 방향이 왼쪽인 온풍기가 있음
		3: 방향이 위인 온풍기가 있음
		4: 방향이 아래인 온풍기가 있음
		5: 온도를 조사해야 하는 칸  
		*/
		
		if(d==1) {
			if(i==0) {
				if(wall[x][y-1].contains(1) || wall[x+1][y-1].contains(0)) return false;
			} else if(i==1) {
				if(wall[x][y-1].contains(1)) return false;
			} else if(i==2) {
				if(wall[x][y-1].contains(1) || wall[x][y-1].contains(0)) return false;
			}
		} else if(d==2) {
			if(i==0) {
				if(wall[x+1][y+1].contains(0) || wall[x][y].contains(1)) return false;
			} else if(i==1) {
				if(wall[x][y].contains(1)) return false;
			} else if(i==2) {
				if(wall[x][y].contains(1) || wall[x][y+1].contains(0)) return false;
			}
		} else if(d==3) {
			if(i==0) {
				if(wall[x+1][y].contains(0) || wall[x+1][y].contains(1)) return false;
			} else if(i==1) {
				if(wall[x+1][y].contains(0)) return false;
			} else if(i==2) {
				if(wall[x+1][y].contains(0) || wall[x+1][y-1].contains(1)) return false;
			}
		} else if(d==4) {
			if(i==0) {
				if(wall[x][y].contains(0) || wall[x-1][y].contains(1)) return false;
			} else if(i==1) {
				if(wall[x][y].contains(0)) return false;
			} else if(i==2) {
				if(wall[x][y].contains(0) || wall[x-1][y-1].contains(1)) return false;
			}
		}
		
		return true;
	}
	
	public static boolean isInside(int x, int y) {
		return x>=0 && y>=0 && x<R && y<C;
	}
	
	public static void print(int[][] m) {
		for(int i=0; i<m.length; i++) {
			for(int j=0; j<m[i].length; j++) {
				System.out.printf("%.3s  ", map[i][j]);
			}
			System.out.println();
		}
		System.out.println();
	}
}