题解 SP15436 【UCV2013H - Slick】
Chinshyo
2020-10-12 23:03:46
这是一道非常经典的**铺地板问题**。说起铺地板，最优选择的就是DFS。让我们来看一下解题思路：
# 搜索过程
首先要明确这道题的求解搜索过程。首先把整张地图用for双重循环扫一遍，每次发现有墨水就开始从该点出发向四周扩展开去。然后，每经过一个点都把该点的墨水消除，或者是标记为已访问过。
如果该点是墨水就可以被访问：
# 输入输出优化
本题输入输出较多，建议使用输入输出优化，本人建议使用这行代码关闭同步流
```cpp
ios::sync_with_stdio(false);
```
# CODE
```cpp
#include<bits/stdc++.h>
using namespace std;
int a[255][255];
int n,m,ans;
void dfs(int dep,int i,int j)
{
ans++;
a[i][j]=0;
if(a[i+1][j]==1) dfs(dep+1,i+1,j);
if(a[i][j+1]==1) dfs(dep+1,i,j+1);
if(a[i-1][j]==1) dfs(dep+1,i-1,j);
if(a[i][j-1]==1) dfs(dep+1,i,j-1);
}
int main()
{
ios::sync_with_stdio(false);
int n,m,k,q;
cin>>n>>m;
memset(a,0x3f,sizeof(a));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
cin>>k>>q;
map <int,int> ma;
int answer=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]==1)
{
ans=0;
dfs(1,i,j);
if(ma.find(ans)!=ma.end())
{
ma.find(ans)->second++;
}
else
{
ma.insert(make_pair(ans,1));
}
}
}
}
for(map<int,int>::iterator i=ma.begin();i!=ma.end();i++)
{
answer=answer+i->second;
}
cout<<answer<<endl;
for(map<int,int>::iterator i=ma.begin();i!=ma.end();i++)
{
cout<<i->first<<" "<<i->second<<endl;
}
return 0;
}
```