Bit Maps

A bitmap is a data structure that appears in many areas of computing. In graphics, for example, a bitmap can represent an image, where a 1 is a black pixel and a 0 is a white pixel.

Consider two ways of representing a rectangular bitmap.

• B (array) form: the bitmap is written directly as a two-dimensional array of 1s and 0s.
• D (decomposition) form: built by the following recursive rule. Look at the whole bitmap. If every bit is 1, output 1. If every bit is 0, output 0. Otherwise output D, split the bitmap into four quarters, and encode each quarter the same way, in the order top-left, top-right, bottom-left, bottom-right.

The quarters are formed as follows. When the region has an even number of rows and an even number of columns, the four quarters have equal size. When the number of columns is odd, the left quarters have one more column than the right quarters. When the number of rows is odd, the top quarters have one more row than the bottom quarters. If a region with only one row or only one column is split, it yields two halves: for a single column, the top half is encoded before the bottom half; for a single row, the left half is encoded before the right half.

Write a program that reads bitmaps given in either form and converts each one to the other form (B to D, and D to B).

The input is a series of bitmaps. Each bitmap starts with a line giving its form (B or D) and its dimensions (the number of rows and the number of columns). Neither dimension exceeds 200. The items on this line are separated by at least one space. The following line or lines contain the sequence of 1, 0, and D characters that make up the bitmap, with no spaces between them. Each of these lines contains exactly 50 characters, except the last, which may be shorter. A B-form bitmap is listed left to right, top to bottom. The input ends with a line containing a single #.

For each input bitmap, output the same bitmap converted to the opposite form: a B-form input becomes D-form output, and a D-form input becomes B-form output. Each converted bitmap begins on a new line with a header: the form letter (D or B), then the number of rows and the number of columns, each right-justified in a field four characters wide. The bitmap data then follows on the next line or lines, written 50 characters per line with the last line possibly shorter.