题目链接:

https://www.luogu.org/problemnew/show/UVA297

附几道推荐题目(先完成再食用此题效果更佳)

https://www.luogu.org/problemnew/show/UVA122

https://www.luogu.org/problemnew/show/UVA699

https://www.luogu.org/problemnew/show/UVA839

分析:

本题为树上的递归题目。我们可以在一个子函数search中完成:

void search(int x,int y,int w)

其中x为当前准备判断像素的正方形的最小x坐标,y同理,w为正方形的边长。


每次判断一个字符,如果是灰色,那么继续往下递归:

if(tmp=='p')
	{
		search(x+w/2,y+w/2,w/2);
		search(x+w/2,y,w/2);
		search(x,y,w/2);
		search(x,y+w/2,w/2);
	}
	因为每次灰色后都再次切成四块,所以说每次w要除以2

否则,就是黑或白,白不用管,只把黑色的像素填上:

else
	{
		if(tmp=='f')
		{
			for(int i=x;i<x+w;i++)
			{
				for(int j=y;j<y+w;j++)
				{
					a[i][j]=1;
				}
			}
		}

这些就是本题的核心部分,还有就是要注意输入输出,初始化等等,在此就不赘述了。

代码:

#include<cstdio>
#include<cstring>
#include<string> 
#include<iostream>
using namespace std;
int cnt=-1;
char s[1005];
int a[33][33];
void search(int x,int y,int w)
{
	char tmp=s[++cnt];
	if(tmp=='p')
	{
		//if(num==1)
		search(x+w/2,y+w/2,w/2);
		//else
		//if(num==2)
		search(x+w/2,y,w/2);
		//else
		//if(num==3)
		search(x,y,w/2);
		//else
		//if(num==4)
		search(x,y+w/2,w/2);
	}
	else
	{
		if(tmp=='f')
		{
			//printf("%d %d %d %d\n",xl,yl,xr,yr);
			for(int i=x;i<x+w;i++)
			{
				for(int j=y;j<y+w;j++)
				{
					a[i][j]=1;
				}
			}
		}
		/*if(num==1) search(xr*2,yr*2,xr,yr,num+1); else if(num==2) search(xl,yr*2,xr*2,yr,num+1); else if(num==3) search(xl,yl,xr*2,yr*2,num+1); else if(num==4) search(xr*2,yl,xr,yr*2,num+1); */
		//search(xl,yl,xr,yr,num+1);
	}
	 
}
int main()
{
	int T;
	scanf("%d\n",&T);
	while(T--)
	{
		cnt=-1;
		memset(a,0,sizeof(a));
		int ans=0;
		cin>>s;
		search(0,0,32);
		cnt=-1;
		cin>>s;
		search(0,0,32);
		for(int i=0;i<=32;i++)
		{
			for(int j=0;j<=32;j++)
			{
				if(a[i][j]==1)
				ans++;
			}
		}
		printf("There are %d black pixels.\n",ans);
	}
	return 0;
}