Lake Counting
来源：POJ
标签：
参考资料：
相似题目：
题目
Due to recent rains, water has pooled in various places in Farmer John’s field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water (‘W’) or dry land (’.’). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors. Given a diagram of Farmer John’s field, determine how many ponds he has.
输入
Line 1: Two space-separated integers: N and M
Lines 2…N+1: M characters per line representing one row of Farmer John’s field. Each character is either ‘W’ or ‘.’. The characters do not have spaces between them.
输出
Line 1: The number of ponds in Farmer John’s field.
输入样例
10 12 W…WW. .WWW…WWW …WW…WW. …WW. …W… …W…W… .W.W…WW. W.W.W…W. .W.W…W. …W…W.
输出样例
3
提示
OUTPUT DETAILS: There are three ponds: one in the upper left, one in the lower left,and one along the right side.
参考代码
#include<stdio.h>
const int maxn
=100+10;
char arr
[maxn
][maxn
];
int vis
[maxn
][maxn
];
int n
,m
;
void dfs(int x
,int y
)
{
vis
[x
][y
]=1;
for(int i
=-1;i
<=1;i
++)
{
for(int j
=-1;j
<=1;j
++)
{
int nx
=x
+i
,ny
=y
+j
;
if(0<=nx
&& nx
<n
&& 0<=ny
&& ny
<m
&& arr
[nx
][ny
]=='W' && !vis
[nx
][ny
])
dfs(nx
,ny
);
}
}
}
int main()
{
scanf("%d%d",&n
,&m
);
int i
,j
;
for(i
=0;i
<n
;i
++)
scanf("%s",arr
[i
]);
int cnt
=0;
for(i
=0;i
<n
;i
++)
{
for(j
=0;j
<m
;j
++)
{
if(arr
[i
][j
]=='W' && !vis
[i
][j
])
{
dfs(i
,j
);
cnt
++;
}
}
}
printf("%d\n",cnt
);
return 0;
}
