Quadtrees UVA 297 四分树

以你之姓@ 2024-02-17 18:53 55阅读 0赞

// 2 1

// 3 4

对于四分树来说，给出了它的先序序列就可以确定整棵树了，因为对任意一个节点不是叶子就是父节点，对于一个父节点一定有四个子节点（就和完全二叉树一样，通过先序就可以确定整棵树了）。

题目大意是：整块的黑色区域的像素是1024，因为有些部分白色，所以通过四等分直到整个小区域都是黑色为止，最小可以分为（32\*32=1024）个，每个小区域表示1像素。所以程序中通过递归不断的分成四等分。

1.  \#include<cstdio>
2.  \#include<cstring>
3.  const int maxn=3000; //不能是紫书上的1024+10；因为叶子最多可能就有1024，整棵树加起来远超过1024 ， 改了之后就AC了，之前一直WR。
4.  const int len=32;
5.  int sum ;
6.  char s\[maxn\];
7.  int buf\[len\]\[len\];
8.  void solve(const char \*s,int &temp,int r,int c,int w)\{ 
9.   char ch=s\[temp++\];
10.  if(ch=='p')\{ 
11.  solve(s,temp,r ,c+w/2,w/2); //1
12.  solve(s,temp,r ,c ,w/2); //2
13.  solve(s,temp,r+w/2,c ,w/2); //3
14.  solve(s,temp,r+w/2,c+w/2,w/2); //4
15.  \}
16.  else if(ch=='f')\{ 
17.  for(int i=r;i<r+w;i++)
18.  for(int j=c;j<c+w;j++)
19.  if(buf\[i\]\[j\]==0)\{ 
20.  sum++;
21.  buf\[i\]\[j\]=1;
22.  \}
23.  \}
24. \}
25. int main()\{ 
26.  int T;
27.  scanf("%d",&T);
28.  while(T--)\{ 
29.  sum=0;
30.  memset(buf,0,sizeof(buf));
31.  for(int i=0;i<2;i++)\{ 
32.  scanf("%s",s);
33.  int temp=0;
34.  solve(s,temp,0,0,len);
35.  memset(s,0,sizeof(s));
36.  \}
37.  printf("There are %d black pixels.\\n",sum);
38.  \}
39.  return 0;
40. \}
41.

如有错误之处还望指出，谢谢!

发表评论取消回复

表情：

评论列表（有 0 条评论，55人围观）

还没有评论，来说两句吧...

相关阅读

相关 UVA 714 Copying Books （二分）

题意：把一个包含m个正整数的序列划分成k个非空的连续子序列，使得每个正整数恰好属于一个序列。设第i个序列的和为S(i)，要找所有S(i)的最大值尽量小。如有多解，S(1)应

秒速五厘米/ 2024年02月17日 22:47/ 0 赞/ 24 阅读

相关 uva11300分金币随机选择算法

题意：ｎ个人围成一圈，每个人都有一些硬币，，每个人只能给左右相邻的人硬币，问最少交换几个硬币，使每个人硬币一样多； //没用随机选择算法也可以过 /

矫情吗；*/ 2024年02月17日 21:21/ 0 赞/ 75 阅读

相关 S-Trees UVA712（二叉树）

题目读了半天，差点被吓住！题目本身很简单，就是一颗满二叉树，向左（2\temp）,向右（2\temp+1），最后减去（1<<n）-1;（即非叶子结点的个数，因为储存叶子结点是从

怼烎@/ 2024年02月17日 19:01/ 0 赞/ 44 阅读

相关 Quadtrees UVA 297 四分树

// 2 1 // 3 4 对于四分树来说，给出了它的先序序列就可以确定整棵树了，因为对任意一个节点不是叶子就是父节点，对于一个父节点一定有四个子节点（就和完全二叉树一样，

以你之姓@/ 2024年02月17日 18:53/ 0 赞/ 56 阅读

相关 UVA 297 Quadtrees

题目链接：[https://vjudge.net/problem/UVA-297][https_vjudge.net_problem_UVA-297] 题意摘自《算法禁赛入门

待我称王封你为后i/ 2023年06月04日 14:54/ 0 赞/ 6 阅读

相关【LeetCode 297】二叉树的序列化与反序列化

题目描述序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重

Dear 丶/ 2022年11月30日 01:42/ 0 赞/ 189 阅读

相关 UVA 11729-Commando War（排序分任务）

Commando War “Waiting for orders we held in the wood, word from the front never came

喜欢ヅ旅行/ 2022年07月15日 01:54/ 0 赞/ 94 阅读

相关 UVA 11729-Commando War（排序分任务）

Commando War “Waiting for orders we held in the wood, word from the front never came

桃扇骨/ 2022年07月15日 01:54/ 0 赞/ 80 阅读

相关 ACM 四叉树 Quadtrees

这个是昨天训练落下的..今早补得.. UVA 297 Quadtrees ![20170718125424855][] ![201707181254337

系统管理员/ 2022年06月12日 06:49/ 0 赞/ 187 阅读

相关 UVA 644 Immediate Decodability【字典树】题解

目录 1.题目 2.代码 1.题目 An encoding of a set of symbols is s

我就是我/ 2021年07月24日 12:06/ 0 赞/ 365 阅读