题解 P6432 【[USACO3.1]形成的区域 Shaping Regions】

· · 题解

自己贡献的题，自己发一波题解！

这道题和铺地毯想法比较类似。我是用 \text{dfs} 来解。每次循环枚举找到图形的边界点（四边形的四个角），以便求面积。然后开二维数组进行枚举每个图形，最后输出。

还算比较裸的 \text{dfs} 题，适合 \text{dfs} 新手们来切，当然 \text{dfs} 只是一种较简单的写法，别的方法当然也可以切掉这道题。好了，挂上代码！

Code: 
#include<bits/stdc++.h>
using namespace std;
int a[1001][5],area[1001],n;
void dfs(int x1,int y1,int x2,int y2,int color,int deep)
{
    while(deep<=n and (x1>=a[deep][2] or y1>=a[deep][3] or x2<=a[deep][0] or y2<=a[deep][1])) deep++;
    if(deep>n)
    {
        area[color]+=(x2-x1)*(y2-y1);
        return;
    }
    if(x1<a[deep][0]) dfs(x1,y1,a[deep][0],y2,color,deep+1),x1=a[deep][0];
    if(y1<a[deep][1]) dfs(x1,y1,x2,a[deep][1],color,deep+1),y1=a[deep][1];
    if(x2>a[deep][2]) dfs(a[deep][2],y1,x2,y2,color,deep+1),x2=a[deep][2];
    if(y2>a[deep][3]) dfs(x1,a[deep][3],x2,y2,color,deep+1),y2=a[deep][3];
}
int A,B,i,j,k;
int main()
{
    scanf("%d%d%d",&A,&B,&n);
    for(i=1;i<=n;i++) scanf("%d%d%d%d%d",&a[i][0],&a[i][1],&a[i][2],&a[i][3],&a[i][4]);
    dfs(0,0,A,B,1,1);
    for(i=1;i<=n;i++) dfs(a[i][0],a[i][1],a[i][2],a[i][3],a[i][4],i+1);
    for(i=1;i<=1000;i++)
    {
        if(area[i]) printf("%d %d\n",i,area[i]);
    }
    return 0;
}