题目1333:考研海报(25分)
- 题目描述:
-
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
算法分析
用一个二维数组表示展板,将被覆盖的地方置为1,然后求0的个数
需要注意的是
1. 海报(x1,y1,x2,y2) 则开始是从x1+1 到x2, y2+1到y2
2.海报超出的部分要进行修正
int LUx = x1>0 ?x1 : 0; int LUy = y1>0 ?y1 : 0; int RDx = x2<len ?x2 : len; int RDy = y2<len ?y2 : len;
源程序
//============================================================================ // Name : judo1333.cpp // Author : wdy // Version : // Copyright : Your copyright notice // Description : Hello World in C++, Ansi-style //============================================================================ #include <iostream> using namespace std; int board[101][101]; void cleanBoard(int len){ for(int i = 0;i<=len;i++){ for(int j =0;j<=len;j++){ board[i][j] = 0; } } } void addPoster(int x1,int y1,int x2,int y2,int len){ int LUx = x1>0 ?x1 : 0; int LUy = y1>0 ?y1 : 0; int RDx = x2<len ?x2 : len; int RDy = y2<len ?y2 : len; for(int i = LUy+1;i<=RDy;i++){ for(int j = LUx+1;j<=RDx;j++){ board[i][j] = 1; } } } void getEmpty(int len){ int empty = 0; for(int i = 1;i<=len;i++){ for(int j =1;j<=len;j++){ if(!board[i][j]){ empty++; } } } std::cout<<empty<<std::endl; } void judo(){ int len; int m; while(std::cin>>len>>m){ cleanBoard(len); int x1; int y1; int x2; int y2; for(int i = 0;i<m;i++){ std::cin>>x1>>y1>>x2>>y2; addPoster( x1, y1, x2, y2, len); } getEmpty(len); } } int main() { judo(); //cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!! return 0; } /************************************************************** Problem: 1333 User: KES Language: C++ Result: Accepted Time:60 ms Memory:1560 kb ****************************************************************/