UVa 297 - Quadtrees

时间:2022-08-27 19:08:21

题目:利用四叉树处理图片,给你两张黑白图片的四叉树,问两张图片叠加后黑色的面积。

分析:搜索、数据结构。把图片分成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的更多相关文章

  1. UVa 297 Quadtrees(树的递归)

    Quadtrees 四分树就是一颗一个结点只有4个儿子或者没有儿子的树 [题目链接]UVa 297 Quadtrees [题目类型]树的递归 &题意: 一个图片,像素是32*32,给你两个先序 ...

  2. UVA&period;297 Quadtrees &lpar;四分树 DFS&rpar;

    UVA.297 Quadtrees (四分树 DFS) 题意分析 将一个正方形像素分成4个小的正方形,接着根据字符序列来判断是否继续分成小的正方形表示像素块.字符表示规则是: p表示这个像素块继续分解 ...

  3. uva 297 quadtrees——yhx

    Quadtrees  A quadtree is a representation format used to encode images. The fundamental idea behind ...

  4. UVA 297 Quadtrees(四叉树建树、合并与遍历)

    <span style="font-size: 18pt; font-family: Arial, Helvetica, sans-serif; background-color: r ...

  5. UVa 297 Quadtrees -SilverN

    A quadtree is a representation format used to encode images. The fundamental idea behind the quadtre ...

  6. UVA - 297 Quadtrees (四分树)

    题意:求两棵四分树合并之后黑色像素的个数. 分析:边建树边统计. #include<cstdio> #include<cstring> #include<cstdlib& ...

  7. 297 - Quadtrees &lpar;UVa&rpar;

    Quadtrees A quadtree is a representation format used to encode images. The fundamental idea behind t ...

  8. UVa 297 &lpar;四分树 递归&rpar; Quadtrees

    题意: 有一个32×32像素的黑白图片,用四分树来表示.树的四个节点从左到右分别对应右上.左上.左下.右下的四个小正方区域.然后用递归的形式给出一个字符串代表一个图像,f(full)代表该节点是黑色的 ...

  9. 【紫书】Quadtrees UVA - 297 四叉树涂色

    题意:前序遍历给出两个像素方块.求两个方块叠加后有几个黑色格子. 题解:每次读进来一个方块,就在二维数组上涂色.每次把白色涂黑就cnt++: 具体递归方法是以右上角坐标与边长为参数,每次通过几何规律往 ...

随机推荐

  1. &lbrack;CF752E&rsqb;Santa Claus and Tangerines(二分答案,dp)

    题目链接:http://codeforces.com/contest/752/problem/E 题意:给n个橘子,每个橘子a(i)片,要分给k个人,问每个人最多分多少片.每个橘子每次对半分,偶数的话 ...

  2. &lpar;转载&rpar;RESTORE DATABASE命令还原SQLServer 2005 数据库

    今天恢复一个SQLServer2008R2,发现问题,然后通过园友的文章解决了问题,特记录备用 原文地址:http://www.cnblogs.com/adandelion/archive/2006/ ...

  3. Leetcode 13 Roman to Integer 字符串处理&plus;STL

    题意:将罗马数字1到3999转化成自然数字,这里用了STL库map将罗马字符映射到自然数字. I,V,X,L,C,D,M -> 1,5,10,50,100,500,1000 m[s[i]]&lt ...

  4. helpDB

    using System; using System.Collections.Generic; using System.Linq; using System.Web; using System.Da ...

  5. radio应用

    1.获取选中值,三种方法都可以: $('input:radio:checked').val(): $("input[type='radio']:checked").val(); $ ...

  6. WP7 MD5加密

    WP7不支持MD5加密,在网上找了一个实现MD5加密的算法. //Copyright (c) Microsoft Corporation. All rights reserved. using Sys ...

  7. Socket 广播

    1.广播端口 Socket中的广播端口是什么意思,是谁对应谁的? 这个广播端口 指定 客户端接收广播消息时要使用的端口号. 参考: 1.快速Python 原型 2.receive UDP broadc ...

  8. 黑马程序员--C&num;中属性和字段&lpar;变量&rpar;的区别

    ---------------------- ASP.Net+Android+IOS开发..Net培训.期待与您交流! ---------------------- 属性为类提供了一种很有用的封装数据 ...

  9. AngularJs之初

    很久以前就听人说起angularjs,但一直都没有深入了解过.直到最近才在自己心里有了一个准确的定义.和相濡以沫多年的函数库JQuery相比,angular更像一个框架.对,就是一个框架,相比之下的话 ...

  10. 【转】sed正则表达式

    1 正则表达式简介 正则表达式(Regular Expression) 是一种描述文本(或字符串)模式的工具.正则表达式常用于查找文本的场合.想想一下我们日常生活中的例子,假如你想从电话本里找一个联系 ...