题目:利用四叉树处理图片,给你两张黑白图片的四叉树,问两张图片叠加后黑色的面积。
分析:搜索、数据结构。把图片分成1024块1*1的小正方形,建立一位数组记录对应小正方形的颜色。
利用递归根据字符串,建立相应四叉树。在建树的过程中,树节点计算当前节点对应的小正方形
编号区间。这里处理类似于线段树,将父节点的区间等分成4份分别对应四棵子树的编号区间。
建树到达叶子时(color为‘f’或者‘e’),直接将颜色数组赋值即可。当树建完时,颜色数组即染色
完毕。将两棵树依次染色到同一数组,统计黑色节点个数即可。
注意:数组大小,防止RE。
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath> using namespace std; int Color[1024]; typedef struct tnode
{
char color;
tnode* child[4];
}tnode;
tnode *root;
tnode Node[1365];
int Count; tnode* dfs( char* word, int &move, int a, int b )
{
tnode* root = &Node[Count ++];
root->color = word[move ++];
if ( root->color == 'p' ) {
int mid = (a+b)>>1;
int m_l = (a+mid)>>1;
int m_r = (mid+b)>>1;
//构建四个子树
root->child[0] = dfs( word, move, a, m_l );
root->child[1] = dfs( word, move, m_l+1, mid );
root->child[2] = dfs( word, move, mid+1, m_r );
root->child[3] = dfs( word, move, m_r+1, b );
}else if ( root->color == 'f' ) {
//叶子节点染色
for ( int i = a ; i <= b ; ++ i )
Color[i] = 1;
}return root;
} int main()
{
int n,move;
char data[1366]; while ( ~scanf("%d",&n) )
for ( int i = 0 ; i < n ; ++ i ) {
for ( int i = 0 ; i < 1024 ; ++ i )
Color[i] = 0; //处理图片1
scanf("%s",data);
Count = 0;
dfs( data, move = 0, 0, 1023 ); //处理图片2
scanf("%s",data);
Count = 0;
dfs( data, move = 0, 0, 1023 ); //统计黑色节点
int sum = 0;
for ( int i = 0 ; i < 1024 ; ++ i )
sum += Color[i];
printf("There are %d black pixels.\n",sum);
} return 0;
}
UVa 297 - Quadtrees的更多相关文章
-
UVa 297 Quadtrees(树的递归)
Quadtrees 四分树就是一颗一个结点只有4个儿子或者没有儿子的树 [题目链接]UVa 297 Quadtrees [题目类型]树的递归 &题意: 一个图片,像素是32*32,给你两个先序 ...
-
UVA.297 Quadtrees (四分树 DFS)
UVA.297 Quadtrees (四分树 DFS) 题意分析 将一个正方形像素分成4个小的正方形,接着根据字符序列来判断是否继续分成小的正方形表示像素块.字符表示规则是: p表示这个像素块继续分解 ...
-
uva 297 quadtrees——yhx
Quadtrees A quadtree is a representation format used to encode images. The fundamental idea behind ...
-
UVA 297 Quadtrees(四叉树建树、合并与遍历)
<span style="font-size: 18pt; font-family: Arial, Helvetica, sans-serif; background-color: r ...
-
UVa 297 Quadtrees -SilverN
A quadtree is a representation format used to encode images. The fundamental idea behind the quadtre ...
-
UVA - 297 Quadtrees (四分树)
题意:求两棵四分树合并之后黑色像素的个数. 分析:边建树边统计. #include<cstdio> #include<cstring> #include<cstdlib& ...
-
297 - Quadtrees (UVa)
Quadtrees A quadtree is a representation format used to encode images. The fundamental idea behind t ...
-
UVa 297 (四分树 递归) Quadtrees
题意: 有一个32×32像素的黑白图片,用四分树来表示.树的四个节点从左到右分别对应右上.左上.左下.右下的四个小正方区域.然后用递归的形式给出一个字符串代表一个图像,f(full)代表该节点是黑色的 ...
-
【紫书】Quadtrees UVA - 297 四叉树涂色
题意:前序遍历给出两个像素方块.求两个方块叠加后有几个黑色格子. 题解:每次读进来一个方块,就在二维数组上涂色.每次把白色涂黑就cnt++: 具体递归方法是以右上角坐标与边长为参数,每次通过几何规律往 ...
随机推荐
-
[CF752E]Santa Claus and Tangerines(二分答案,dp)
题目链接:http://codeforces.com/contest/752/problem/E 题意:给n个橘子,每个橘子a(i)片,要分给k个人,问每个人最多分多少片.每个橘子每次对半分,偶数的话 ...
-
(转载)RESTORE DATABASE命令还原SQLServer 2005 数据库
今天恢复一个SQLServer2008R2,发现问题,然后通过园友的文章解决了问题,特记录备用 原文地址:http://www.cnblogs.com/adandelion/archive/2006/ ...
-
Leetcode 13 Roman to Integer 字符串处理+STL
题意:将罗马数字1到3999转化成自然数字,这里用了STL库map将罗马字符映射到自然数字. I,V,X,L,C,D,M -> 1,5,10,50,100,500,1000 m[s[i]]< ...
-
helpDB
using System; using System.Collections.Generic; using System.Linq; using System.Web; using System.Da ...
-
radio应用
1.获取选中值,三种方法都可以: $('input:radio:checked').val(): $("input[type='radio']:checked").val(); $ ...
-
WP7 MD5加密
WP7不支持MD5加密,在网上找了一个实现MD5加密的算法. //Copyright (c) Microsoft Corporation. All rights reserved. using Sys ...
-
Socket 广播
1.广播端口 Socket中的广播端口是什么意思,是谁对应谁的? 这个广播端口 指定 客户端接收广播消息时要使用的端口号. 参考: 1.快速Python 原型 2.receive UDP broadc ...
-
黑马程序员--C#中属性和字段(变量)的区别
---------------------- ASP.Net+Android+IOS开发..Net培训.期待与您交流! ---------------------- 属性为类提供了一种很有用的封装数据 ...
-
AngularJs之初
很久以前就听人说起angularjs,但一直都没有深入了解过.直到最近才在自己心里有了一个准确的定义.和相濡以沫多年的函数库JQuery相比,angular更像一个框架.对,就是一个框架,相比之下的话 ...
-
【转】sed正则表达式
1 正则表达式简介 正则表达式(Regular Expression) 是一种描述文本(或字符串)模式的工具.正则表达式常用于查找文本的场合.想想一下我们日常生活中的例子,假如你想从电话本里找一个联系 ...