自动搬运

查看原文

来自洛谷，原作者为

	Lithium_Chestnut 这个家伙很家伙，什么都没有什么。

搬运于2025-08-24 22:20:44，当前版本为作者最后更新于2020-04-20 15:21:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

这道题和铺地毯想法比较类似。我是用 $\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;
}