POJ 2386 Lake Counting(DFS:求8连通分量的个数)

POJ 2386 Lake Counting(DFS:求8连通分量的个数)

http://poj.org/problem?id=2386

题意:给你一个N*M的字符网格,要你求该网格中有多少个有字符’w’构造的8连通分量.

分析:直接DFS求出连通分量个数即可.之前很多题目与本题类似.

AC代码:

#include<cstdio>
using namespace std;
const int maxn=100+5;
char grid[maxn][maxn];
int R,C;
int ans;
void dfs(int r,int c)
{
    if(r<0||r>=R||c<0||c>=C||grid[r][c]!='W')
        return ;
    grid[r][c]='.';
    dfs(r,c+1);
    dfs(r,c-1);
    dfs(r+1,c);
    dfs(r-1,c);
    dfs(r+1,c+1);
    dfs(r-1,c-1);
    dfs(r+1,c-1);
    dfs(r-1,c+1);
}
int main()
{
    while(scanf("%d%d",&R,&C)==2)
    {
        for(int i=0;i<R;i++)
            scanf("%s",grid[i]);
        ans=0;
        for(int i=0;i<R;i++)
        for(int j=0;j<C;j++)if(grid[i][j]=='W')
        {
            ans++;
            dfs(i,j);
        }
        printf("%d\n",ans);
    }
    return 0;
}