비트맵

비트맵(bitmap)은 컴퓨팅의 여러 분야에서 쓰이는 자료 구조이다. 예를 들어 그래픽 분야에서 비트맵은 이미지를 나타낼 수 있는데, 이때 1은 검은 픽셀을, 0은 흰 픽셀을 뜻한다.

직사각형 비트맵을 나타내는 두 가지 방식을 생각하자.

• B(배열) 형식: 비트맵을 1과 0으로 이루어진 2차원 배열로 그대로 적는다.
• D(분할) 형식: 다음 재귀 규칙으로 만든다. 먼저 비트맵 전체를 본다. 모든 비트가 1이면 1을 출력한다. 모든 비트가 0이면 0을 출력한다. 그렇지 않으면 D를 출력한 뒤 비트맵을 네 개의 사분면으로 나누고, 각 사분면을 같은 방식으로 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서로 처리한다.

사분면은 다음과 같이 나눈다. 행의 수와 열의 수가 모두 짝수이면 네 사분면의 크기가 모두 같다. 열의 수가 홀수이면 왼쪽 사분면이 오른쪽보다 열을 하나 더 갖는다. 행의 수가 홀수이면 위쪽 사분면이 아래쪽보다 행을 하나 더 갖는다. 행이 하나뿐이거나 열이 하나뿐인 영역을 나누면 두 개의 절반이 생긴다. 열이 하나뿐이면 위쪽 절반을 아래쪽보다 먼저 처리하고, 행이 하나뿐이면 왼쪽 절반을 오른쪽보다 먼저 처리한다.

두 형식 중 어느 것으로 주어지든 비트맵을 읽어 다른 형식으로 변환하는(B는 D로, D는 B로) 프로그램을 작성하라.

입력은 여러 개의 비트맵으로 이루어진다. 각 비트맵은 형식(B 또는 D)과 크기(행의 수와 열의 수)를 적은 줄로 시작한다. 두 크기 모두 200을 넘지 않는다. 이 줄의 각 항목은 적어도 하나의 공백으로 구분된다. 그 다음 줄(들)에는 비트맵을 이루는 1, 0, D 문자들이 공백 없이 이어서 나온다. 이들 각 줄은 정확히 50개의 문자를 담으며, 마지막 줄만 더 짧을 수 있다. B 형식 비트맵은 왼쪽에서 오른쪽으로, 위에서 아래로 나열된다. 입력은 # 한 글자만 있는 줄로 끝난다.

각 입력 비트맵에 대해, 그 비트맵을 반대 형식으로 변환하여 출력한다. 즉 B 형식 입력은 D 형식으로, D 형식 입력은 B 형식으로 변환한다. 변환된 각 비트맵은 새 줄에서 머리글 줄로 시작한다. 머리글 줄에는 형식 문자(D 또는 B)에 이어 행의 수와 열의 수를 각각 너비 4의 필드에 오른쪽 정렬하여 적는다. 그 다음 줄(들)에 비트맵 데이터를 한 줄에 50개 문자씩(마지막 줄은 더 짧을 수 있음) 적는다.