最大的湖

Link” nowcoder-910-D
Description:
农场主约翰的农场在最近的一场风暴中被洪水淹没,这一事实只因他的奶牛极度害怕水的消息而恶化。

然而,他的保险公司只会根据他农场最大的“湖”的大小来偿还他一笔钱。

农场表示为一个矩形网格,有N(1≤N≤100)行和M(1≤M≤100)列。网格中的每个格子要么是干的,

要么是被淹没的,而恰好有K(1≤K≤N×M)个格子是被淹没的。正如人们所期望的,一个“湖”有一个

中心格子,其他格子通过共享一条边(只有四个方向,对角线不算的意思)与之相连。任何与中央格子共享一条边或与中央格

子相连的格子共享一条边的格子都将成为湖的一部分。

输入描述:
第一行有三个整数N,M,K,分别表示这个矩形网格有N行,M列,K个被淹没的格子。

接下来K行,每一行有两个整数R,C。表示被淹没的格子在第R行,第C列。
输出描述:
输出最大的“湖”所包含的格子数目
示例1
输入
3 4 5
3 2
2 2
3 1
2 3
1 1
输出
4

Intentional analysis:
My solution to this problem is According to the input structure diagram and then proceed BFS.

Click to see Chinese Intentional analysis 通过输入构造图然后进行BFS。为了防止各种绕弯,我对下标进行了操作。

Code:

#include<bits/stdc++.h>
using namespace std;
char s[105][105];
int d[4][2]={0,-1, -1,0, 0,1, 1,0};
bool flag[105][105];
int n,m,k,a,b,anss=0;
queue<pair<int,int> > que;
#define pil pair<int,int>
int bfs(int x,int y)
{
    memset(flag,0,sizeof(flag));
    flag[x][y]=1;
    int ans=1;
    que.push(pil(x,y));
    while(!que.empty())
    {
        x=que.front().first;
        y=que.front().second;
        que.pop();
        for(int i=0;i<4;i++)
        {
            int xx=x+d[i][0];
            int yy=y+d[i][1];
            if(xx<0||yy<0||xx>=n||yy>=m||s[xx][yy]=='#'||flag[xx][yy]==1)    continue;
            else
            {
                flag[xx][yy]=1;
                ans++;
                que.push(pil(xx,yy));
            }
        }
    }
    return ans;
}
int main()
{
    cin>>n>>m>>k;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            s[i][j]='#';
        }
    while(k--)
    {
        cin>>a>>b;
        s[a-1][b-1]='@';
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(s[i][j]=='@')
            anss=max(bfs(i,j),anss);
        }
    }
    cout<<anss<<endl;
}