#P2266. Quadtree
Quadtree
本题没有可用的提交语言。
描述
在一座古老的阿兹特克遗迹中寻找宝藏时,佛罗里达·琼斯(著名的印第安纳·琼斯的兄弟)偶然发现了一卷写有一长串符号的纸莎草纸卷轴。这串符号中包含三种不同的符号,在这里我们将它们称为 B、W 和 Q。
由于在密码学方面有一定经验,佛罗里达·琼斯立刻认出这个密码就是 3000 年前发明的著名四叉树编码方案。
在四叉树系统中,秘密图片(如藏宝图)是按以下方式编码的:如果整张图片是黑色的,就用字母 B 编码;如果是全白色的,就用 W 编码;如果两种颜色都有使用(通常是这种情况),则用 Qxxxx 编码,其中每个 x 是一个字符串,用于递归地对图片的四分之一进行编码(顺序为左上、右上、左下、右下)。由于阿兹特克人总是使用边长为(是 2 的幂)像素的正方形图片,所以这种方法总是能完美地工作。
例如,一个 2×2 的棋盘会被编码为 QWBBW,一个 4×4 的棋盘会被编码为 QQWBBWQWBBWQWBBWQWBBW。
你的任务是对四叉树字符串进行解码,并以 XBM 格式输出图片(见输出说明)。
输入
第一行包含一个整数(),表示图片每行/每列的像素大小。始终是 2 的幂。
第二行是一个由字母 B、W 和 Q 组成的字符串。该字符串使用四叉树方案对一个像素的图片进行了编码。
输出
第一行打印 "#define quadtree_width ",其中是输入中给出的图片大小。
第二行相应地打印 "#define quadtree_height "。
第三行打印 "static char quadtree_bits[] = {"。
然后,打印行(每行编码图片的一行像素),每行有个十六进制数。
每个十六进制数由 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。()
每个十六进制数后面打印一个逗号。
最后一行打印 "}"。
注意:示例输出中用 /* 和 */ 括起来的注释不是输出的一部分,它们有助于解释 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