九度题目1333:考研海报-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

九度题目1333:考研海报

简介:

题目1333:考研海报

时间限制:1 秒

内存限制:32 兆

特殊判题:否

提交:645

解决:256

题目描述:

sun是万千考研学子中的一员,他每天过着三点一线的生活。

学校里有一个公告栏,他每天都看到上面张贴着各种考研海报。

sun提出了一个问题:公告栏上还剩多少空白区域是没被考研海报张贴过的?

于是sun果断上王道贴上了这道题目。

 
输入:

公告栏左上角是坐标原点(0,0),公告栏长宽相等。

数据有多组,每组输入公告栏长度n(0<n<=100)。

海报张数m(0<m<=100),以及每张海报的左上角坐标(x1,y1)和右下角坐标(x2,y2)。

注意:其中坐标有可能小于0,大于n,但在int范围内。

 
输出:

对每一组输入输出公告栏还剩多少空白区域,输出带回车。

 
样例输入:

3

2

0 0 1 2

0 0 2 1

10

2

0 0 1 1

0 0 3 3
样例输出:

6

91

 

 

思路:将边长为n的矩形划分为一块一块的小方块,一共(n*n块)。如图一边长为3的矩形有3*3块块小矩形

图一(加输入样例1)

每一块小矩形的表示方式即为左上角坐标和右下角坐标加一个唯一判定坐标(防止图二情况发生),只要

记录广告覆盖掉哪几个坐标下的方块就可以得出剩下空白的区域面积了。

左上角坐标由a[]数组记录,右下角坐标由b[]数组记录,唯一判定坐标由f[]数组记录

 

图2(如果不加唯一判定坐标会出现多算一个方块的情况)

3 2

0 0 1 1

2 2 3 3

正确答案是2

但是不加f[]得到的是3

原因:方块一的右下坐标被标记,

方块二的左上坐标被标记,

如果只以这两组坐标作为方块被覆盖的依据的话,

中间就会出现一个假的(其实没有被覆盖)方块,

它的左上坐标和右下坐标都被标记了。

所以要加一个能唯一判定方块的判定坐标(f[]标记左上方x和右下方y),

这样就不会出现这种情况。

 
AC代码:

#include<stdio.h>
#include<string.h>
int a[202][202],b[202][202],f[101][101];
int main()
{
	int i,j,n,m,sum,x1,y1,x2,y2,p,k,v,u;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(f,0,sizeof(f));
		for(i=0;i<m;i++)
		{
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			if(x1<n&&y1<n&&x2<=n&&y2<=n&&x1>=0&&y1>=0&&x2>0&&y2>0)//由于坐标会超出范围,所以要确定坐标范围
			{				
				for(p=x1;p<x2;p++)//左上方x坐标
				   for(k=y1;k<y2;k++)//左上方y坐标
				   {
					   a[p][k]=1;//左上方x坐标和左上方y坐标
					   b[p+1][k+1]=1;//右下方x坐标和右下方y坐标
					   f[p][k+1]=1;//防止图2得情况发生,要加一个判定坐标
				   }
			}
			else
			{
				//将超出范围的坐标缩小到所给范围内在计算
				if(x2>n||y2>n)
				{
					while(!(x2<=n&&y2<=n))
					{
						if(x2>n)
						x2--;
						if(y2>n)
						y2--;
					}

				}
				
				if(x1<0||y1<0)
				{
                    while(!(x1>=0&&y1>=0))
					{
						if(x1<0)
						x1++;
						if(y1<0)
						y1++;
					}
				}

				for(p=x1;p<x2;p++)//左上方x坐标
				   for(k=y1;k<y2;k++)//左上方y坐标
				   {
					   a[p][k]=1;//左上方x坐标和左上方y坐标
					   b[p+1][k+1]=1;//右下方x坐标和右下方y坐标
					   f[p][k+1]=1;//防止图2得情况发生,要加一个判定坐标
				   }
			}
		}
        int sum=0;
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
			{
				//找到没有被占位的,记录
				if(a[i][j]==0&&b[i+1][j+1]==0&&f[i][j+1]==0)
					sum++;
			}
			printf("%d\n",sum);
	}
	return 0;
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章