Quadtree II
Time Limit: 2 Seconds
Memory Limit: 65536 KB
Having realized that the quadtree-encoded treasure map was a fake, Florida Jones
maliciously plans to also play a prank for the next treasure hunter after him.
But for that, he needs your help once again:
Can you write a program that takes a picture in the XBM format and encodes
it with the quadtree scheme?
Input
- The first line will be "#define quadtree_width n" where n is
the picture size in pixels. (The picture is quadratic: n*n pixels)
- The second line will be "#define quadtree_height n" accordingly.
- The third line will be "static char quadtree_bits[] = {".
- Then, n lines will follow, each one encoding one pixel row of the picture.
There will be n/8 hexadecimal numbers per line.
Each hexadecimal number is composed of 8 bits that encode 8 pixels from left
to right (where the leftmost bit has the value 1 and the rightmost bit has
the value 128). The hexadecimal numbers are printed in the form 0xdd where
d is one character of the set { 0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f }.
Example: The 8 pixels WBBBBWWB are written as 0x9e. (2+4+8+16+128 = 158 =
0x9e)
After each hexadecimal number, a comma follows.
- The last line will be "};".
Output
First, print the integer n (8 <= n <= 512) on a line by itself.
Then, print a string consisting of the letters B, W and Q that correctly encodes
the picture with the quadtree scheme.
Finally, terminate the string with a newline character.
Sample Input
Note: The comments (enclosed by /* and */) are not part of the input. They should
help to explain the XBM format.
#define quadtree_width 16
#define quadtree_height 16
static char quadtree_bits[] = {
0xf0,0xf0, /* WWWWBBBB WWWWBBBB */
0xf0,0xf0, /* WWWWBBBB WWWWBBBB */
0xf0,0xf0, /* WWWWBBBB WWWWBBBB */
0xf0,0xf0, /* WWWWBBBB WWWWBBBB */
0x0f,0x0f, /* BBBBWWWW BBBBWWWW */
0x0f,0x0f, /* BBBBWWWW BBBBWWWW */
0x0f,0x0f, /* BBBBWWWW BBBBWWWW */
0x0f,0x0f, /* BBBBWWWW BBBBWWWW */
0xf0,0xf0, /* WWWWBBBB WWWWBBBB */
0xf0,0xf0, /* WWWWBBBB WWWWBBBB */
0xf0,0xf0, /* WWWWBBBB WWWWBBBB */
0xf0,0xf0, /* WWWWBBBB WWWWBBBB */
0x0f,0x0f, /* BBBBWWWW BBBBWWWW */
0x0f,0x0f, /* BBBBWWWW BBBBWWWW */
0x0f,0x0f, /* BBBBWWWW BBBBWWWW */
0x0f,0x0f, /* BBBBWWWW BBBBWWWW */
};
Sample Output
16
QQWBBWQWBBWQWBBWQWBBW
Source:
University of Ulm Local Contest 1999
Submit
Status