ACM 四叉树 Quadtrees

系统管理员 2022-06-12 06:49 171阅读 0赞

这个是昨天训练落下的..今早补得..

**UVA 297 Quadtrees**

**![20170718125424855][]**

**![20170718125433785][]**

**![20170718125440848][]**

**题目大意：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);
    	}
    }

[20170718125424855]: /images/20220612/5fc32cfcf4034694bd0176970139b45b.png
[20170718125433785]: /images/20220612/b8ddd584bd1c41c19c11efd3d527b622.png
[20170718125440848]: /images/20220612/c6dfb64f7f6d4328b0b3d11f2e6f7752.png