生命不息,奋斗不止

题解 SP15436 【UCV2013H - Slick】

2020-10-12 23:03:46


这是一道非常经典的铺地板问题。说起铺地板,最优选择的就是DFS。让我们来看一下解题思路:

搜索过程

首先要明确这道题的求解搜索过程。首先把整张地图用for双重循环扫一遍,每次发现有墨水就开始从该点出发向四周扩展开去。然后,每经过一个点都把该点的墨水消除,或者是标记为已访问过。

如果该点是墨水就可以被访问:

输入输出优化

本题输入输出较多,建议使用输入输出优化,本人建议使用这行代码关闭同步流

ios::sync_with_stdio(false);

CODE

#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;
}