pku3620 Avoid The Lakes(简单搜索)

题目：

题目大意是说将一块由N*M个单元格组成的矩形，中有些矩形格是潮湿的，有些是干燥的。并给出其中潮湿的单元格的位置，现在要求出最大的连在一起的潮湿区域中包含有多少个单元格。这种类型的题目很多，或作为其它算法的预处理。实现原理如下，对每一个符合要求的单元格搜出其相联的区域，并进行标记，记录下该区域的大小。。最后记录下最大的大的区域大小。具体的见代码，就能体会。感觉就像是在用模板。

my code:

 

#include<iostream>
using namespace std;
int n,m,k,a,b,t,ans;
bool use[101][101],map[101][101];
int pos[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
bool In(int x,int y)//判断x,y是否在矩形范围内
{
    return x>=1&&x<=n&&y>=1&&y<=m;
}
void res(int x,int y)//搜索到当前的位置
{
    int i;
    use[x][y]=1;t++;//标记并将总的个数加1
    for(i=0;i<4;i++)//搜索相邻的四个位置
    {
        a=pos[i][0]+x;
        b=pos[i][1]+y;
        if(In(a,b)&&!use[a][b]&&map[a][b])
            res(a,b);
    }
}
void sea()//找出未搜索过的块，进行搜索标记

{
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(!use[i][j]&&map[i][j])//从一个点搜索出包含该点的块
            {
                t=0;res(i,j);
                if(ans<t)ans=t;
            }
}
int main()
{
    int i,j;
    while(cin>>n>>m>>k)
    {
        for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        map[i][j]=use[i][j]=0;
        for(i=1;i<=k;i++)
        {
            cin>>a>>b;
            map[a][b]=1;
        }
        ans=0;sea();
        cout<<ans<<endl;
    }
    return 0;
}

PS：虽然这样写比较直观，也比较容易构造代码，但递归效率不高，本题耗时141MS,而很多人是0MS，这就是差距哇。。