欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

四分树( Quadtrees, UVa 297)

程序员文章站 2022-06-09 21:30:04
...

如图6-8所示, 可以用四分树来表示一个黑白图像, 方法是用根结点表示整幅图像, 然后把行列各分成两等分, 按照图中的方式编号, 从左到右对应4个子结点。 如果某子结点对应的区域全黑或者全白, 则直接用一个黑结点或者白结点表示; 如果既有黑又有白, 则用一个灰结点表示, 并且为这个区域递归建树。
四分树( Quadtrees, UVa 297)
给出两棵四分树的先序遍历, 求二者合并之后( 黑色部分合并) 黑色像素的个数。 p表示中间结点, f表示黑色( full) , e表示白色( empty)。
样例输入:
3
ppeeefpffeefe
pefepeefe
peeef
peefe
peeef
peepefefe
样例输出:
There are 640 black pixels.
There are 512 black pixels.
There are 384 black pixels.
【分析】
由于四分树比较特殊, 只需给出先序遍历就能确定整棵树( 想一想, 为什么)。 只需要编写一个“画出来”的过程, 边画边统计即可。

#include"pch.h"
#include<iostream>
#include<cstdio>
#include<cstring>

const int len = 32;
const int maxn = 1024 + 10;
char s[maxn];
int buf[len][len], cnt;

// 把字符串s[p..]导出到(r,c)为左上角,边长为w的缓冲区
// 2 1
// 3 4
void draw(const char* s, int& p, int r, int c, int w) {
	char ch = s[p++];
	if (ch == 'p') {
		draw(s, p, r, c + w / 2, w / 2);// 1
		draw(s, p, r, c, w / 2);// 2
		draw(s, p, r + w / 2, c, w / 2);// 3
		draw(s, p, r + w / 2, c + w / 2, w / 2);// 4
	}
	else if (ch == 'f') {
		for (int i = r; i < r + w; i++)
			for (int j = c; j < c + w; j++)
				if (buf[i][j] == 0) {
					buf[i][j] = 1;
					cnt++;
				}
	}
}

int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		memset(buf, 0, sizeof(buf));
		cnt = 0;
		for (int i = 0; i < 2; i++) {
			scanf("%s", s);
			int p = 0;
			draw(s, p, 0, 0, len);
		}
		printf("There are %d black pixels.\n", cnt);
	}
	return 0;
}