本文主要是介绍ACM 四叉树 Quadtrees，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这个是昨天训练落下的..今早补得..
UVA 297 Quadtrees
题目大意：p是分叉，f是涂色，e是空白，给出一个32*32的方块，求填涂面积。（四叉就是四分）
我的是用递归，把画的过程模拟出来..
#include <stdio.h>
#include <string.h>
const int len=32;
const int maxn=1024+10;
char s[maxn];
int map[len][len],sum;
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);draw(s,p,r,c,w/2);draw(s,p,r+w/2,c,w/2);draw(s,p,r+w/2,c+w/2,w/2);}else if(ch=='f'){for(int i=r;i<r+w;i++){for(int j=c;j<c+w;j++){if(map[i][j]==0){map[i][j]=1;sum++;}}}}
}
int main()
{int n,i,j,p;scanf("%d",&n);while(n--){sum=0;memset(map,0,sizeof(map));for(i=0;i<2;i++){scanf("%s",s);p=0;draw(s,p,0,0,len);}printf("There are %d black pixels.\n",sum);}
}下面是学姐用队列写的...
#include<stdio.h>
#include<queue>
#include<stack>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
struct mm
{int x,y,c;
}p,q,b,w;
queue<mm> add(char *a)
{b.c=2,w.c=1;stack<mm>h;queue<mm>f;int i,s=strlen(a),j;p.x=0,p.y=1,p.c=0;h.push(p);for(i=0;i<s;i++){if(a[i]=='p'){while(a[i]=='p'){if(!h.empty()){p=h.top();h.pop();for(j=4;j>=1;j--){q.x=p.x+1;q.y=4*p.y+j-3;q.c=0;h.push(q);}}i++;}}if(a[i]=='e'){p=h.top();h.pop();p.c=1;for(j=0;j<1024/pow(4,p.x);j++)f.push(w);}if(a[i]=='f'){p=h.top();h.pop();p.c=2;for(j=0;j<1024/pow(4,p.x);j++)f.push(b);}}return f;
}
int main()
{int t,i,s;char a[5000],b[5000];queue<mm>f,g;scanf("%d",&t);while(t--){s=0;scanf("%s%s",a,b);f=add(a);g=add(b);while(!f.empty()){p=f.front();f.pop();q=g.front();g.pop();if(p.c==2||q.c==2)s++;}//printf("%d %d\n",f.size(),g.size());printf("There are %d black pixels.\n",s);}
}
这篇关于ACM 四叉树 Quadtrees的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
