[백준]20058 마법사 상어와 파이어 스톰

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109

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

public class B20058 {
	static int N, Q, sum, count, max;
	static int arr[][], delta[][] = {{0,1},{1,0},{0,-1},{-1,0}};
	static boolean[][] visit, check;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken());
		arr = new int[1<<N][1<<N];
		for (int i = 0; i < 1<<N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 1<<N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < Q; i++) {
			int K  = Integer.parseInt(st.nextToken());
			rotate(K);
			melt();
		}
		
		// 다른 것에 포함되었는지 확인 여부
		visit = new boolean[1<<N][1<<N];
		
		for (int i = 0; i < 1<<N; i++) {
			for (int j = 0; j < 1<<N; j++) {
				visit[i][j] = true;
				sum+=arr[i][j];
				// 시작이 0인지 여부
				count=arr[i][j]!=0?1:0;
				counting(i,j);
				max = Math.max(count, max);
			}
		}
		
		System.out.println(sum+"\n"+max);
	}
	
	// 나눠진 구간에 대해 90도 회전
	private static void rotate(int r) {
		int[][] copy  = new int[1<<N][1<<N];
		int k = 1<<r;
		for(int i=0;i<1<<N;i+=k) {
			for(int j=0;j<1<<N;j+=k) {
				for(int a = 0; a < k; a++) {
                    for(int b = 0; b < k ; b++) {
                        copy[i+b][j+k-a-1] = arr[i+a][j+b];
                    }
                }
			}
		}
		arr = copy;
	}
	
	public static void melt() {
		// 녹일 얼음 찾을 배열
        check = new boolean[1<<N][1<<N];
        for(int i = 0; i < 1<<N; i++) {
            for(int j = 0; j < 1<<N; j++) {
				// 0일 때 skip
            	if(arr[i][j]==0) continue;
                int count = 0;
                for(int k = 0; k < 4; k++) {
                    int nx = i + delta[k][0];
                    int ny = j + delta[k][1];
                    // 주변에 얼음이 있으면 counting
                    if(inside(nx, ny) && arr[nx][ny] >= 1)
                    	count++;
                }
                
				// 3면보다 작은거 체크
                if(count < 3) {
                    check[i][j] = true;
                }
            }
        }
        
        for(int i = 0; i < 1<<N; i++) {
            for(int j = 0; j < 1<<N; j++) {
            	if(check[i][j]) arr[i][j]--;
            }
        }
    }
	// dfs : 붙어있는 얼음 개수 세기
	private static void counting(int x, int y) {
		for(int d=0;d<4;d++) {
			int nx = x + delta[d][0];
			int ny = y + delta[d][1];
			
			if(inside(nx,ny)&&!visit[nx][ny] && arr[nx][ny]>=1) {
				visit[nx][ny] = true;
				count++;
				counting(nx,ny);
			}
		}
	}
    
    public static boolean inside(int x, int y) {
        return x >= 0 && y >= 0 && x < 1<<N && y < 1<<N;
    }
}