【四分树（ Quadtrees, UVa 297）】如图6-8所示， 可以用四分树来表示一个黑白图像， 方法是用根结点表示整幅图像， 然后把行列各分成两等分， 按照图中的方式编号， 从左到右对应4个子结点。 如果某子结点对应的区域全黑或者全白， 则直接用一个黑结点或者白结点表示； 如果既有黑又有白， 则用一个灰结点表示， 并且为这个区域递归建树。
文章图片
给出两棵四分树的先序遍历， 求二者合并之后（ 黑色部分合并） 黑色像素的个数。 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
#include
#includeconst 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;
}
推荐阅读
- c/c++|有感 Visual Studio 2015 RTM 简介 - 八年后回归 Dot Net，终于迎来了 Mvc 时代，盼走了 Web 窗体时代...
- C/C++|C/C++ basis 02
- Qt实战|Qt+OpenCV联合开发（二十一）--图像翻转与旋转
- Qt实战|Qt+OpenCV联合开发（十四）--图像感兴趣区域（ROI）的提取
- Qt实战|Qt+OpenCV联合开发（十三）--通道分离与合并
- opencv|Qt+OpenCV联合开发（十六）--图像几何形状绘制
- Qt实战|Qt+OpenCV联合开发（十七）--随机数与随机颜色
- SNAT的MASQUERADE地址选择与端口选择
- IPTABLES的连接跟踪与NAT分析
- IPVS分析