#P2266. Quadtree

Quadtree

本题没有可用的提交语言。

描述

在一座古老的阿兹特克遗迹中寻找宝藏时,佛罗里达·琼斯(著名的印第安纳·琼斯的兄弟)偶然发现了一卷写有一长串符号的纸莎草纸卷轴。这串符号中包含三种不同的符号,在这里我们将它们称为 B、W 和 Q。

由于在密码学方面有一定经验,佛罗里达·琼斯立刻认出这个密码就是 3000 年前发明的著名四叉树编码方案。

在四叉树系统中,秘密图片(如藏宝图)是按以下方式编码的:如果整张图片是黑色的,就用字母 B 编码;如果是全白色的,就用 W 编码;如果两种颜色都有使用(通常是这种情况),则用 Qxxxx 编码,其中每个 x 是一个字符串,用于递归地对图片的四分之一进行编码(顺序为左上、右上、左下、右下)。由于阿兹特克人总是使用边长为nnnn是 2 的幂)像素的正方形图片,所以这种方法总是能完美地工作。

例如,一个 2×2 的棋盘会被编码为 QWBBW,一个 4×4 的棋盘会被编码为 QQWBBWQWBBWQWBBWQWBBW。

你的任务是对四叉树字符串进行解码,并以 XBM 格式输出图片(见输出说明)。

输入

第一行包含一个整数nn8n5128 \leq n \leq 512),表示图片每行/每列的像素大小。nn始终是 2 的幂。

第二行是一个由字母 B、W 和 Q 组成的字符串。该字符串使用四叉树方案对一个n×nn \times n像素的图片进行了编码。

输出

第一行打印 "#define quadtree_width nn",其中nn是输入中给出的图片大小。

第二行相应地打印 "#define quadtree_height nn"。

第三行打印 "static char quadtree_bits[] = {"。

然后,打印nn行(每行编码图片的一行像素),每行有n/8n/8个十六进制数。

每个十六进制数由 8 位组成,从左到右对 8 个像素进行编码(其中最左边的位值为 1,最右边的位值为 128)。十六进制数应以 0xdd 的形式打印,其中 d 是集合 { 0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f } 中的一个字符。

示例:8 个像素 WBBBBWWB 应写为 0x9e。(2+4+8+16+128=158=0x9e2 + 4 + 8 + 16 + 128 = 158 = 0x9e

每个十六进制数后面打印一个逗号。

最后一行打印 "}"。

注意:示例输出中用 /* 和 */ 括起来的注释不是输出的一部分,它们有助于解释 XBM 格式。

示例

输入

16
QQWBBWQWBBWQWBBWQWBBW

输出

#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 */
};

提示

Unix 工具 xv 可以显示 XBM 格式的图形。

所以,在你完成程序后,使用 "quadtree | xv -" 运行它,查看图片,这可能有助于调试。

来源

乌尔姆本地赛 1999