종이의 개수

시간 제한2초메모리 제한256 MB

요약
-1, 0, 1로 채워진 N x N 격자를 같은 값이 아닐 때마다 9등분으로 재귀적으로 나눠서 각 값으로만 이루어진 조각의 개수를 구하는 문제입니다.
난이도

보통10점 중 5점

유형
분할 정복, 재귀, 행렬, 구현
정답자
아직 제출이 없습니다

문제

N×N 크기의 정사각형 종이가 있다. 종이는 행렬로 표현되며, 각 칸에는 -1, 0, 1 중 하나가 적혀 있다.

종이는 다음 규칙에 따라 자른다.

  1. 현재 종이의 모든 칸에 같은 수가 적혀 있다면, 그 종이는 더 자르지 않고 그대로 사용한다.
  2. 그렇지 않다면 현재 종이를 같은 크기의 정사각형 9개로 나누고, 나뉜 각 종이에 같은 과정을 반복한다.

자르는 과정이 모두 끝났을 때, -1로만 이루어진 종이의 개수, 0으로만 이루어진 종이의 개수, 1로만 이루어진 종이의 개수를 각각 구하시오.

입력

첫째 줄에 N이 주어진다. N은 1 이상 3^7 이하이며, 3의 거듭제곱이다.

다음 N개의 줄에는 종이를 나타내는 행렬이 주어진다. 각 줄에는 -1, 0, 1 중 하나인 정수 N개가 공백으로 구분되어 주어진다.

출력

첫째 줄에 -1로만 이루어진 종이의 개수를 출력한다.

둘째 줄에 0으로만 이루어진 종이의 개수를 출력한다.

셋째 줄에 1로만 이루어진 종이의 개수를 출력한다.

예제1

  1. 예제 1

    입력
    9
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
0 1 -1 0 1 -1 0 1 -1
0 -1 1 0 1 -1 0 1 -1
0 1 -1 1 0 -1 0 1 -1
    예상 출력
    10
12
11