POJ 3620 Avoid The Lakes（dfs算法）

题意：给出一个农田的图，n行m列，再给出k个被淹没的坐标( i , j )。求出其中相连的被淹没的农田的最大范围。

思路：dfs算法

代码：

#include<iostream>
#include<stdio.h>
using namespace std;
int t[150][150];
int visit[150][150];
int n,m,k;
int dfs(int i,int j){
if(i<1||j<1||i>n||j>m||t[i][j]==0||visit[i][j]==1)
return 0;
visit[i][j]=1;
int sum=1;
sum=sum+dfs(i-1,j);
sum=sum+dfs(i+1,j);
sum=sum+dfs(i,j-1);
sum=sum+dfs(i,j+1);
return sum;
}
int main(){
scanf("%d%d%d",&n,&m,&k);
int i,j;
int max=0;
int sum;
while(k--){
scanf("%d%d",&i,&j);
t[i][j]=1;
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(t[i][j]==1&&visit[i][j]==0){
sum=dfs(i,j);
if(sum>max)
max=sum;
}
printf("%d\n",max);
return 0;
}