点击打开链接
题目意思:给定两个字符串,字符p对应建立子树,字符e为白色,f为黑色对于不同层黑点f对应不同的值,最上面为1024下来为每个子树256.....,这样建立两颗四叉树,计算两颗树相加后的黑点f对应的值,注意在两颗树上同一点处,只要有一个为黑点,那么相加后就为黑
解题思路:1首先建立两颗树,采用递归建树的方法 2建完树后利用前序遍历的方法进行递归求解和
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <deque>
#include <algorithm>
using namespace std;
const int MAXN = 1000010;//定义一个常量
//4叉树的结构体
struct Btree{
char c;
struct Btree *child[4];//四叉我们开个数组存储四个子树
};
Btree *root1 , *root2;//两颗树的根节点
char str1[MAXN] , str2[MAXN];//存储读入的两串字符串
int l1 , l2 , sum , pos;
//4叉树的初始华
void newnode(Btree *u){
u -> c = 0;
for(int i = 0 ; i < 4 ; i++)
u -> child[i] = NULL;
}
//树的递归建立
Btree* BuildTree(Btree *root , char *str){//返回Btree*
++pos;//pos要为全局,注意递归的全局和局部变量区别
if(pos == strlen(str))//如果达到字符串末尾则返回NULL
return NULL;
root = new Btree;//每一New一个
newnode(root);//new出来要习惯初始化
root -> c = str[pos];//根节点的值为str[pos]
if(str[pos] == 'p'){//如果为p则建立子树,否则直接返回根节点就好
for(int i = 0 ; i < 4 ; ++i){
if(root->child[i] == NULL){//如果哪个子树为空则递归产生子树
root->child[i] = BuildTree(root->child[i] , str);
}
}
}
return root;
}
//前序求和(同时遍历两颗树)
void preorder(Btree *root1 , Btree *root2 , int level){
if(root1 == NULL && root2 == NULL)//如果两颗树此时都为空则直接返回
return;
if(root1 == NULL){//树1为空时候
if(root2->c == 'f'){//如果当前树2的值为f要加上值1024>>(level*2)
sum += 1024>>(level*2);//位运算的使用
return;//为f 说明子树为空直接返回即可
}
for(int i = 0 ; i < 4 ; i++)//否则遍历子树2的四个方向
preorder(root1 , root2->child[i] , level+1);
return;//记得每一次都要返回
}
if(root2 == NULL){//同上
if(root1->c == 'f'){
sum += 1024>>(level*2);
return;
}
for(int i = 0 ; i < 4 ; i++)
preorder(root1->child[i] , root2 , level+1);
return;
}
//如果此时要个都不为空只要有一个是f就要加上对应值
if(root1->c == 'f' || root2->c == 'f'){
sum += 1024>>(level*2);
return;//返回上一层
}
for(int i = 0 ; i < 4 ; i++)//四个方向的遍历
preorder(root1->child[i] , root2->child[i] , level+1);
}
//输入函数
void solve(){
pos = -1;
root1 = new Btree;
root2 = new Btree;
newnode(root1);//初始化
newnode(root2);
root1 = BuildTree(root1 , str1);//建树
root2 = BuildTree(root2 , str2);//建树
sum = 0;
preorder(root1 , root2 , 0);
printf("There are %d black pixels.\n" , sum);
}
//主函数
int main(){
int t;
scanf("%d" , &t);
while(t--){
scanf("%s%s" , str1 , str2);//输入两串字符串
solve();
}
return 0;
}
分享到:
相关推荐
四叉树例子(几乎不大不小JavaScript库)与 。四叉树 如何使用您可以下载quadtree.js并将其包含在您的p5草图中,或通过以下CDN链接进行引用: <... </ script > 一旦包含了库,就可以创建一个具有Rectangle...
正弦信号的matlab代码使用DCT和四叉树进行图像压缩 简介图像压缩:图像压缩可最大程度地减小图形文件的字节大小,而不会降低图像质量到不可接受的水平。 文件大小的减小允许在给定数量的磁盘或内存空间中存储更多...
BentoMap是四叉树quadtrees的实现,用于地图标注集群和存储采用Swift开发。
quadtree-js, 另一个用于javascript的四叉树实现 四叉树 js这是本教程中介绍的Java方法的JavaScript四叉树实现: http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-
You'll dive deep into how scripting engines encode behavior, how quadtrees and other spatial partitions optimize your engine, and how other classic design patterns can be used in games. Table of ...
QuadTrees空间细分 广相碰撞检测 分离轴定理 窄相碰撞检测 瓷砖引擎 精灵系统 渲染动画图像和纯色。 附加功能 Emscript6模块减小包装尺寸 附加模块 资产模块 加载图像,音频和json文件。 输入模块 捕获键盘输入 ...
生活质量简介/恢复该库实现了Quadtrees和Octrees(以Point和Region两种形式)的简单版本,该库是出于教育目的而创建的,请不要尝试在生产系统中使用它。 可以轻松实现四方树和八叉树形式的简易图书馆(点对点地区的...
Continuous LOD terrain meshing using adaptive quadtrees 770 2D surface deformation 782 Lone game developper battles physics simulator 795 Collision response : bouncy, trouncy, fun 801 Simultaneous ...
4.30 Quadtrees 461 4.31 Quadrisection 478 4.32 Space-Filling Curves 485 4.33 Hilbert Scan and VQ 487 4.34 Finite Automata Methods 497 4.35 Iterated Function Systems 513 4.36 Cell Encoding 529 xxiv ...