이미지 압축

흰색과 검은색으로만 이루어진 이미지는 쿼드트리로 표현할 수 있다. 쿼드트리의 루트는 전체 이미지를 나타낸다. 어떤 영역이 모두 같은 색이면 그 색을 나타내는 하나의 정점으로 표현한다. 그렇지 않으면 영역을 네 개의 같은 크기 영역으로 나누고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서로 네 자식 정점을 둔다. 각 자식 영역에도 같은 규칙을 재귀적으로 적용한다.

이미지의 세로 길이와 가로 길이가 같지 않거나, 한 변의 길이가 2의 거듭제곱이 아닐 수 있다. 이때는 원래 이미지를 왼쪽 위에 둔 채, 오른쪽과 아래쪽을 흰색으로 채워서 정사각형을 만든다. 정사각형의 한 변은 원래 이미지의 두 길이 이상인 가장 작은 2의 거듭제곱이다. 예를 들어 5 x 13 이미지는 16 x 16 이미지로 확장되고, 추가된 칸은 모두 흰색이다.

쿼드트리 자체도 이미지를 압축하지만, 같은 모양의 부분 트리가 여러 번 나타나면 그 부분 트리를 한 번만 저장하고 나머지는 포인터로 연결해 더 줄일 수 있다. 이때 서로 같은 부분 트리는 실제로 나타낸 영역의 크기가 달라도, 트리의 모양과 색 배치가 같으면 같은 것으로 본다.

단, 색 하나를 나타내는 B 또는 W 정점은 포인터가 아니라 값 자체이므로, 정점이 하나뿐인 트리는 공유해도 압축으로 보지 않는다. 즉, 같은 색의 단일 정점들을 하나로 합쳐 세지 않는다.

이미지가 주어졌을 때, 일반 쿼드트리의 정점 수와, 위 규칙으로 가능한 가장 적은 정점 수를 구하시오.

첫째 줄에 이미지의 크기를 나타내는 두 정수 n, m이 주어진다. n과 m은 각각 1 이상 128 이하이며, 이미지는 n x m 크기이다.

다음 n개의 줄에는 길이 m의 문자열이 주어진다. 각 문자는 0 또는 1이며, 0은 흰색, 1은 검은색을 뜻한다.

첫째 줄에 일반 쿼드트리의 정점 수와 가장 효율적으로 압축한 쿼드트리의 정점 수를 공백으로 구분해 출력한다.