现在的位置: 首页 > 综合 > 正文

九度笔记之 1333:考研海报(25分)

2014年01月31日 ⁄ 综合 ⁄ 共 1733字 ⁄ 字号 评论关闭

题目1333:考研海报(25分)

时间限制:1 秒

内存限制:32 兆

特殊判题:

提交:544

解决:201

题目描述:

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
****************************************************************/


抱歉!评论已关闭.