문제
남극의 겨울은 매우 춥다.
이 추위를 펭귄은 어떻게 이겨낼까?
열손실을 줄이기 위해 겹겹이 모이는 허들링(huddling)이란 방법을 사용한다.
바깥쪽의 펭귄의 체력이 떨어질 때 쯤이면 안쪽에 체력을 보충한 펭귄과 자리를 바꾼다.
가상의 펭귄들이 2N × 2N 크기의 각 격자에 모여있다고 가정해보자.
위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 펭귄의 체력을 의미한다.
A[r][c]가 0인 경우 빈 자리라고 하자.
그리고 떨어진 체력은 획복되지 않는다고 가정한다.
가상의 펭귄들이 허들링 하는 방법은 다음과 같다.
리더 펭귄의 신호에 따라 모든 펭귄은 전체 구역을 소구역으로 나누고
각 구역의 펭귄들은 시계방향으로 90도 회전하여 자리를 재배치한다.
리더 펭귄은 재배치를 하기 위해 매번 구간의 크기 L을 외친다.
펭귄들은 이 신호에 따라 전체 구역을 (1, 1)부터 시작하여 2L × 2L 크기의 소구역으로 나눈다.
그리고 각 소구역의 펭귄들은 시계방향으로 90도 회전하여 자리를 재배치한다.
이후 상하좌우 인접한 위치에 있는 펭귄의 수가 3 미만인 경우 체력이 1줄어든다.
(r, c)와 인접한 칸은 (r-1, c), (r+1, c), (r, c-1), (r, c+1)이다.
체력이 바닥난 펭귄은 소멸하고 그 자리는 빈 자리가 된다.
시간이 지남에 따라 소멸하는 펭귄이 늘어남에 따라 펭귄은 몇 개의 소 그룹으로 나뉘어질 수 있다.
아래 그림을 보자.
1번 그림은 N = 3일때, 64마리의 펭귄이 모여 있는 초기 모습이다.
2번 그림은 리더 펭귄이 L = 1을 외친 이후 소구역 펭귄들이 자리를 재배치한 결과이다.
3, 4 번 그림은 상하좌우 인접한 위치에 있는 펭귄의 수가 3미안인 경우 체력이 1줄어든 결과이다.
5번 그림은 3번 이후에 리더 펭귄이 L = 2를 외친 후 소구역 펭귄들이 자리를 재배치한 결과이다.
6번 그림은 상하좌우 인접한 위치에 있는 펭귄의 수가 3미안인 경우 체력이 1줄어든 결과이다.
리더펭귄은 신호를 Q번 외치고 난 후 다음 두 가지 결과를 구하여 출력하는 프로그램을 작성하시오.
1. 남아있는 펭귄들의 체력의 총합
2. 가장 많은 펭귄이 포함된 소그룹의 펭귄수
(r, c)와 인접한 칸은 (r-1, c), (r+1, c), (r, c-1), (r, c+1)이며
인접한 칸에 있는 두 펭귄은 같은 소그룹에 포함된다.
입력
첫째 줄에 N과 Q가 주어진다.
둘째 줄부터 2N개의 줄에는 격자의 각 칸에 있는 펭귄의 체력이 주어진다.
r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.
마지막 줄에는 리더 펭귄이 외친 수 L1, L2, ..., LQ가 순서대로 주어진다.
[제한조건]
2 ≤ N ≤ 6
1 ≤ Q ≤ 1,000
0 ≤ A[r][c] ≤ 100
0 ≤ Li ≤ N
출력
첫째 줄에 남아있는 펭귄들의 체력의 총합을 출력하고,
둘째 줄에 가장 많은 펭귄이 포함된 소그룹의 펭귄수를 출력한다.
예제 #1
3 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1
284
64
예제 #2
3 2
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2
280
64
예제 #3
3 5
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 0 3 2
268
64
예제 #4
3 10
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 0 3 2 1 2 3 2 3
248
62
예제 #5
3 10
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
1 2 3 1 2 3 1 2 3 1
246
60
예제 #6
3 10
1 0 3 4 5 6 7 0
8 0 6 5 4 3 2 1
1 2 0 4 5 6 7 0
8 7 6 5 4 3 2 1
1 2 3 4 0 6 7 0
8 7 0 5 4 3 2 1
1 2 3 4 5 6 7 0
0 7 0 5 4 3 2 1
1 2 3 1 2 3 1 2 3 1
37
9
로그인해야 코드를 작성할 수 있어요.