牛客910D（最大的湖）dfs

链接：https://ac.nowcoder.com/acm/contest/910/D 来源：牛客网  

题目描述

农场主约翰的农场在最近的一场风暴中被洪水淹没，这一事实只因他的奶牛极度害怕水的消息而恶化。

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

 

农场表示为一个矩形网格，有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

代码：  

#include<bits/stdc++.h> using namespace std; int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; int a[200][200]; int n,m,k; int sum; void dfs(int x,int y) { for(int i=0;i<=3;i++) { int nx=x+dx[i]; int ny=y+dy[i]; if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]==1) { a[nx][ny]=0; sum++; dfs(nx,ny); } } } int main() { cin>>n>>m>>k; memset(a,0,sizeof(a)); int x,y; for(int i=1;i<=k;i++) { cin>>x>>y; a[x][y]=1; } int maxx=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(a[i][j]==1) { a[i][j]=0; sum=1; dfs(i,j); maxx=max(maxx,sum); } } cout<<maxx<<endl; }