NOI openjudge 2405:Avoid The Lakes

题目翻译

农夫约翰的农场在最近的一场风暴中被洪水淹没，这一事实只因他的奶牛极度怕水而更加恶化。然而，他的保险公司只会根据他农场上最大的“湖”的大小来偿还他。

农场被表示为一个矩形网格，有N（1<=N<=100）行和M（1<=M<=100）列。网格中的每个单元要么是干燥的，要么是浸没的，其中恰好有K个单元（1<=K<=N*M）被浸没。正如人们所料，湖泊有一个中心单元，其他单元通过共享一条长边（而不是一个角）与之相连。任何与*单元共享长边或与任何连接单元共享长边的单元都将成为连接单元，并且是湖泊的一部分。

输入

第1行：三个空格分隔的整数：N、M和K

第2行到第K+1行：第i+1行描述了一个浸没位置，其中有两个空格分隔的整数，分别是其行和列：R和C

输出

第1行：最大湖泊包含的单元数。

样例

输入

3 4 5
3 2
2 2
3 1
2 3
1 1

输出

4

解题思路

爆搜，走过的地方不能再走一次，只搜索之前没走过的点就可以了

代码示例

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,m,k;
int x,y;
int a[110][110];
int ans;
int cnt;

void dfs(int x,int y){
	cnt++;
	a[x][y]=0;
	if(a[x][y+1]) dfs(x,y+1);
	if(a[x][y-1]) dfs(x,y-1);
	if(a[x+1][y]) dfs(x+1,y);
	if(a[x-1][y]) dfs(x-1,y);
}

int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=k;i++){
		cin>>x>>y;
		a[x][y]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]){
				cnt=0;
				dfs(i,j);
				ans=max(ans,cnt);
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}