[BOJ] 17144. 미세먼지 안녕!

import java.util.Scanner;

public class Main {
	static int[] dx = {1,0,-1,0};
	static int[] dy = {0,1,0,-1};
	static int[] cleaner = new int [2];
	static int map[][];
	static int copyMap[][];
	static int R,C;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		R = sc.nextInt();
		C = sc.nextInt();
		int T = sc.nextInt();		
		
		map = new int[R][C];
		copyMap = new int[R][C];
		int count = 0;
		for(int i = 0; i < R; i++) {
			for(int j = 0; j < C; j++) {
				map[i][j] = sc.nextInt();
				if(map[i][j] == -1) {					
					cleaner[count] = i;					
					count++;
				}
			}
		}
		
		for(int t = 0; t < T; t++) {
			copy(map,copyMap);
			for(int i = 0; i < R; i++) {
				for(int j = 0; j < C; j++) {
					if(map[i][j] != 0 || map[i][j] != -1) {
						spread(i,j,cleaner[0],cleaner[1]);						
					}
				}
			}			
			rotate1(cleaner[0]);
			rotate2(cleaner[1]);		
		}					
		
		int answer = 0;
		for(int i = 0; i < R; i++) {
			for(int j = 0; j < C; j++) {
				if(map[i][j] != -1) {
					answer += map[i][j];
				}
			}
		}
		
		System.out.println(answer);
	}
	
	public static void copy(int[][] map,int[][] copyMap) {
		for(int i = 0; i < map.length; i++) {
			for(int j = 0; j < map[0].length; j++) {
				copyMap[i][j] = map[i][j];
			}
		}
	}		
	
	public static int aroundCount(int y, int x, int cleaner_y1, int cleaner_y2) {
		int count = 0;
		for(int i = 0; i < dx.length; i++) {
			int next_y = y + dy[i];
			int next_x = x + dx[i];
			if(!isOutOfBound(next_y, next_x) & !isCleanerLocation(next_y,next_x,cleaner_y1,cleaner_y2)) count++;
		}
		return count;
	}
	
	public static void spread(int y, int x, int cleaner_y1, int cleaner_y2 ) {
		int current_num = copyMap[y][x];
		if(current_num == 0) return;
		
		int spread_num = aroundCount(y,x,cleaner_y1,cleaner_y2);
		for(int i = 0; i < dx.length; i++) {
			int next_y = y + dy[i];
			int next_x = x + dx[i];
			if(!isOutOfBound(next_y,next_x) && !isCleanerLocation(next_y,next_x,cleaner_y1,cleaner_y2)) {
				map[next_y][next_x] += current_num/5; 
			}			
		}
		map[y][x] = map[y][x] - (current_num/5)*spread_num;
	}
	
	public static boolean isOutOfBound(int y, int x) {
		if(y < 0 || y >= R || x < 0 || x >= C) return true;
		return false;
	}
	
	public static boolean isCleanerLocation(int y, int x, int cleaner_y1, int cleaner_y2) {
		if(x == 0 && (y == cleaner_y1 || y == cleaner_y2)) return true;
		return false;
	}
	
	public static void rotate1(int cleaner_y1) {
		for(int i = cleaner_y1 - 1; i >= 0; i--) {
			if(map[i+1][0] != -1) map[i+1][0] = map[i][0];			
		}
		
		for(int i = 1; i < C; i++) {
			if(map[0][i-1] != -1) map[0][i-1] = map[0][i];
		}
		
		for(int i = 1; i <= cleaner_y1; i++) {
			map[i-1][C-1] = map[i][C-1];
		}
		
		for(int i = C-2; i >= 0; i--) {
			if(map[cleaner_y1][i] != -1) map[cleaner_y1][i+1] = map[cleaner_y1][i];
		}
		map[cleaner_y1][1] = 0;
	}
	
	public static void rotate2(int cleaner_y2) {
		for(int i = cleaner_y2 + 1; i < R - 1; i++) {
			if(map[i][0] != -1) map[i][0] = map[i+1][0];
		}
		
		for(int i = 1; i < C; i++) {
			if(map[R-1][i-1] != -1) map[R-1][i-1] = map[R-1][i];
		}
		
		for(int i = R-2; i >= cleaner_y2;i--) {		
			map[i+1][C-1] = map[i][C-1];			
		}
		
		for(int i = C-1; i >= 1; i--) {
			if(map[cleaner_y2][i-1] != -1) map[cleaner_y2][i] = map[cleaner_y2][i-1];
		}
		map[cleaner_y2][1] = 0;
	}
}