이미지 압축

2차원 이미지를 압축하는 여러 기법은 서로 비슷한 넓은 영역을 찾아내는 데 바탕을 둔다. 이 문제에서는 비트맵 이미지를 계층적으로(사분트리, quadtree) 분할하는 한 가지 방법을 다룬다. 이미지의 각 픽셀은 두 색 중 하나이며, 0(흰색)과 1(검은색)으로 나타낸다.

이미지는 트리로 부호화한다. 루트는 정사각형 전체 영역을 나타낸다. 어떤 영역이 단색(모든 픽셀이 같은 색)이면 그 영역에 해당하는 노드는 그 색을 저장하는 리프가 된다. 그렇지 않으면 영역을 중심을 기준으로 크기가 같은 네 개의 사분면으로 나누고, 각 사분면에 같은 절차를 재귀적으로 적용한다.

이 방식은 무손실 압축이지만, 한 가지만 바꾸면 손실 압축으로 쓸 수 있다. 영역을 완전한 단색이 될 때까지 분할하는 대신 정수 임계값 $T$(백분율)를 정한다. 어떤 영역에서 한 색이 전체 픽셀의 $T%$ 이상을 차지하면 그 영역은 곧바로 리프가 되고, 그 다수 색을 리프에 저장한다. 두 색 모두 $T%$에 이르지 못할 때만 영역을 사분면으로 나누어 재귀적으로 처리한다. 픽셀 하나짜리 영역은 항상 한 색이 100%이므로 이 과정은 반드시 끝난다.

이렇게 부호화한 결과로부터 이미지를 복원(압축 해제)할 때는, 각 리프 영역을 그 리프에 저장된 색으로 전부 채운다.

원본 비트맵과 임계값이 주어질 때, 이 손실 압축으로 압축한 뒤 다시 복원한 이미지를 출력하여라.

$T$가 항상 51 이상이므로 임계값에 도달할 수 있는 색은 많아야 하나뿐이며, 리프의 색은 결코 모호하지 않다.

입력은 여러 개의 데이터 집합으로 이루어지며, 마지막에는 0 하나만 있는 줄이 온다.

각 데이터 집합의 첫 줄에는 두 정수 $W$와 $T$가 있다. $W$는 비트맵의 너비이고 $T$는 임계값 백분율이다. 모든 이미지는 정사각형이며, $W$는 2의 거듭제곱으로 $1 \le W \le 64$이다. 임계값은 $51 \le T \le 100$을 만족한다.

$W$와 $T$가 있는 줄 다음에는 $W$개의 줄이 이어지며, 각 줄은 정확히 $W$개의 문자로 이루어진 문자열로 각 문자는 0 또는 1이고, 비트맵의 한 행을 위에서 아래 순서로 나타낸다.

각 데이터 집합마다 먼저 Image k: 형태의 줄을 출력한다. 여기서 $k$는 데이터 집합의 번호로 1부터 시작한다. 그다음 $W$개의 줄을 출력하며, 각 줄은 복원된 비트맵의 한 행을 위에서 아래 순서로 0과 1 문자열로 나타낸다.