3.1.4 Shaping Regions 形成的区域

3.1.4 Shaping Regions 形成的区域

时间： 1ms        内存：64M

描述：

N个不同的颜色的不透明的长方形(1 <= N <= 1000)被放置在一张宽为A长为B的白纸上。 这些长方形被放置时，保证了它们的边于白纸的边缘平行。 所有的长方形都放置在白纸内，所以我们会看到不同形状的各种颜色。 坐标系统的原点(0,0)设在这张白纸的左下角，而坐标轴则平行于边缘。

输入：

每行输入的是放置长方形的方法。
第一行输入的是那个放在底的长方形(即白纸)。

第 1 行: A ， B 和 N, 由空格分开 (1 <=A, B<=10,000) 第 2 到N+1行: 为五个整数　llx, lly, urx, ury, color　这是一个长方形的左下角坐标，右上角坐标和颜色。 颜色 1和底部白纸的颜色相同。

输出：

输出文件应该包含一个所有能被看到颜色连同该颜色的总面积的清单( 即使颜色的区域不是连续的)，按color的增序顺序。
不要显示没有区域的颜色。

示例输入：

20 20 3
2 2 18 18 2
0 8 19 19 3
8 0 10 19 4

示例输出：

1 91
2 84
3 187
4 38

提示：

参考答案（内存最优[1276]）：

#include <iostream>
#include <queue>
#include <cstdlib>
using namespace std;

typedef struct
{
    int llx;
    int lly;
    int urx;
    int ury;
    int color;
}rect;

int a,b,n;
queue <rect> q1,q2;
int res[1010];

bool judge(rect r)
{
    if((r.urx>r.llx)&&(r.ury>r.lly))
        return true;
    else
        return false;
}

int main()
{
    rect currect,currectc,inputrect;
    int tmpx1,tmpy1,tmpx2,tmpy2;
    int i;
    cin>>a>>b>>n;
    currect.llx=0;
    currect.lly=0;
    currect.urx=a;
    currect.ury=b;
    currect.color=1;
    q1.push(currect);
    for(i=0;i<n;i++)
    {
        cin>>inputrect.llx>>inputrect.lly>>inputrect.urx>>inputrect.ury>>inputrect.color;
        q2.push(inputrect);
        while(!q1.empty())
        {
            currect=q1.front();
            q1.pop();

            if((currect.llx>=inputrect.urx)||(currect.urx<=inputrect.llx)
                ||(currect.lly>=inputrect.ury)||(currect.ury<=inputrect.lly))
            {
                q2.push(currect);
                continue;
            }

            tmpx1=max(currect.llx,inputrect.llx);
            tmpx2=min(currect.urx,inputrect.urx);
            tmpy1=max(currect.lly,inputrect.lly);
            tmpy2=min(currect.ury,inputrect.ury);

            currectc.llx=currect.llx;
            currectc.lly=tmpy1;
            currectc.urx=tmpx1;
            currectc.ury=currect.ury;
            currectc.color=currect.color;
            if(judge(currectc)==true)
                q2.push(currectc);

            currectc.llx=tmpx1;
            currectc.lly=tmpy2;
            currectc.urx=currect.urx;
            currectc.ury=currect.ury;
            currectc.color=currect.color;
            if(judge(currectc)==true)
                q2.push(currectc);

            currectc.llx=tmpx2;
            currectc.lly=currect.lly;
            currectc.urx=currect.urx;
            currectc.ury=tmpy2;
            currectc.color=currect.color;
            if(judge(currectc)==true)
                q2.push(currectc);

            currectc.llx=currect.llx;
            currectc.lly=currect.lly;
            currectc.urx=tmpx2;
            currectc.ury=tmpy1;
            currectc.color=currect.color;
            if(judge(currectc)==true)
                q2.push(currectc);
        }
        while(!q2.empty())
        {
            currect=q2.front();
            q2.pop();
            q1.push(currect);
        }
    }
    while(!q1.empty())
    {
        currect=q1.front();
        q1.pop();
        res[currect.color]+=((currect.urx-currect.llx)*(currect.ury-currect.lly));
    }
    for(i=1;i<=1010;i++)
        if(res[i]!=0)
            cout<<i<<" "<<res[i]<<endl;
    return 0;
}

参考答案（时间最优[32]）：

#include <iostream>
#include <queue>
#include <cstdlib>
using namespace std;

typedef struct
{
    int llx;
    int lly;
    int urx;
    int ury;
    int color;
}rect;

int a,b,n;
queue <rect> q1,q2;
int res[1010];

bool judge(rect r)
{
    if((r.urx>r.llx)&&(r.ury>r.lly))
        return true;
    else
        return false;
}

int main()
{
    rect currect,currectc,inputrect;
    int tmpx1,tmpy1,tmpx2,tmpy2;
    int i;
    cin>>a>>b>>n;
    currect.llx=0;
    currect.lly=0;
    currect.urx=a;
    currect.ury=b;
    currect.color=1;
    q1.push(currect);
    for(i=0;i<n;i++)
    {
        cin>>inputrect.llx>>inputrect.lly>>inputrect.urx>>inputrect.ury>>inputrect.color;
        q2.push(inputrect);
        while(!q1.empty())
        {
            currect=q1.front();
            q1.pop();

            if((currect.llx>=inputrect.urx)||(currect.urx<=inputrect.llx)
                ||(currect.lly>=inputrect.ury)||(currect.ury<=inputrect.lly))
            {
                q2.push(currect);
                continue;
            }

            tmpx1=max(currect.llx,inputrect.llx);
            tmpx2=min(currect.urx,inputrect.urx);
            tmpy1=max(currect.lly,inputrect.lly);
            tmpy2=min(currect.ury,inputrect.ury);

            currectc.llx=currect.llx;
            currectc.lly=tmpy1;
            currectc.urx=tmpx1;
            currectc.ury=currect.ury;
            currectc.color=currect.color;
            if(judge(currectc)==true)
                q2.push(currectc);

            currectc.llx=tmpx1;
            currectc.lly=tmpy2;
            currectc.urx=currect.urx;
            currectc.ury=currect.ury;
            currectc.color=currect.color;
            if(judge(currectc)==true)
                q2.push(currectc);

            currectc.llx=tmpx2;
            currectc.lly=currect.lly;
            currectc.urx=currect.urx;
            currectc.ury=tmpy2;
            currectc.color=currect.color;
            if(judge(currectc)==true)
                q2.push(currectc);

            currectc.llx=currect.llx;
            currectc.lly=currect.lly;
            currectc.urx=tmpx2;
            currectc.ury=tmpy1;
            currectc.color=currect.color;
            if(judge(currectc)==true)
                q2.push(currectc);
        }
        while(!q2.empty())
        {
            currect=q2.front();
            q2.pop();
            q1.push(currect);
        }
    }
    while(!q1.empty())
    {
        currect=q1.front();
        q1.pop();
        res[currect.color]+=((currect.urx-currect.llx)*(currect.ury-currect.lly));
    }
    for(i=1;i<=1010;i++)
        if(res[i]!=0)
            cout<<i<<" "<<res[i]<<endl;
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。