UVA297 四分树 Quadtrees 题解

题目链接:

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;
}
全部评论

相关推荐

mq2:我倒是觉得这种敞亮一点好。能接受就去不能就不去呗。 完了跟现在“正常”公司一样,hr说的天花乱坠,进去一看根本就是996核动力牛马,想走又没应届生身份了。岂不是更糟。
点赞 评论 收藏
分享
ALEX_BLX:虽然说聊天记录不可信,不过这个趋势确实如此但我觉得也要想到一点就是卷后端的人里真正有“料”的人又有多少,我说的这个料都不是说一定要到大佬那种级别,而是就一个正常的水平。即使是现在也有很多人是跟风转码的,2-3个月速成后端技术栈的人数不胜数,但今时不同往日没可能靠速成进大厂了。这种情况就跟考研一样,你能上考场就已经打败一半的人了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务