시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 13 2 2 100.000%

문제

흰색과 검은색으로 이루어진 이미지는 쿼드트리를 이용하여 표현할 수 있다. 쿼드트리의 루트는 이미지의 전체를 나타낸다. 만약 전체 이미지가 한 색깔로 이루어져 있으면, 그 색깔에 해당하는 정점을 루트로 한다. 그 외의 경우에는 그림을 넷으로 나누고, 각각의 나눠진 그림을 루트의 네 자식 정점으로 표현하면 된다. 이 때 첫 번째 자식이 왼쪽 위의 그림을, 두 번째 자식이 오른쪽 위의 그림을, 세 번째 자식이 왼쪽 아래의 그림을, 네 번째 자식이 오른쪽 아래의 그림을 표현하게 된다. 각각의 작은 이미지를 표현할 때도 같은 방법을 재귀적으로 적용한다.

위의 예는 4×4 크기의 이미지와 그에 해당하는 쿼드트리이다. 위의 예에서는 이미지의 크기(사각형의 변의 길이)가 2의 k승이라서 상관이 없었지만, 그 외의 경우에는 문제가 된다. 만약에 이미지의 크기가 2의 k승이 아닐 경우에는, 이미지의 크기를 오른쪽과 아래쪽으로 가장 가까운 2의 k승으로 늘린 뒤, 흰색으로 나머지 공간을 채우면 된다. 이 때 이미지가 정사각형 모양이 되도록 한다. 예를 들어 5×13의 이미지는 16×16 크기의 이미지가 되고, 원래의 이미지가 왼쪽 위에 들어가고 나머지 공간은 흰색으로 채우면 된다.

쿼드트리 자체가 이미지를 압축적으로 표현하는 방법이지만, 우리는 압축된 쿼드트리를 이용하여 좀 더 효율적으로 표현하려 한다. 만약 쿼드트리에서 같은 모양의 부분 트리가 여러 개 나올 경우, 이를 한 번만 저장한 뒤 나머지는 포인터로 연결할 수 있다. 위의 예는 다음과 같은 압축된 쿼드트리로 표현할 수 있다.

원래의 쿼드트리는 17개의 정점을 갖지만, 압축된 쿼드트리는 12개의 정점을 갖는다. 12개의 정점을 갖는 압축된 쿼드트리가 몇 개 더 있기는 하지만, 11개 이하의 정점을 갖는 압축된 쿼드트리는 존재하지 않는다. 따라서 위의 경우가 가장 효율적(정점 개수가 최소)이다.

주의할 것은, B나 W로 표현되는 정점은 포인터가 아니가 값 자체이므로 이를 연결할 경우는 압축하는 것이 아니다. 즉, 정점이 하나인 경우(높이가 1인 경우)에는 포인터를 이용하여 연결할 필요가 없다. 또, 실제 이미지의 크기가 다르더라도 트리의 모양이 같다면, 같은 쿼드트리로 표현될 수 있는데, 이런 경우에도 포인터로 연결할 수 있다.

이미지가 주어졌을 때, 쿼드트리의 정점의 개수와 가장 효율적인 압축된 쿼드트리의 정점의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 이미지의 크기를 나타내는 두 정수 n(1≤n≤128), m(1≤m≤128)이 주어진다. 이는 이미지의 크기가 n×m이라는 의미이다. 다음 n개의 줄에는 m개의 숫자로 이미지가 주어진다. 흰색은 0으로, 검은색은 1로 표현된다.

출력

첫째 줄에 쿼드트리의 정점의 개수와 가장 효율적인 압축된 쿼드트리의 정점의 개수를 출력한다.

예제 입력

4 4
1011
0111
1010
0111

예제 출력

17 12

힌트