题目链接：

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;

}

巴特西

UVA297 四分树 Quadtrees 题解

题目链接：

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

分析：

代码：

最新文章

热门文章