Lak3 Counting(POJ No.2386)

问题描述:

有个大小为N*M的园子，雨后积起了水。八连通的积水被认为是连接在一起的。求出园子里总共有多少水洼。

N, M <= 100

输入例：

：

问题分析：

八连通即：上、左上、左，左下，下，右下，右，右上。

这道题可以用深入优先搜索（DFS）的思想。

　　1. 寻找是水洼的点。如果找到，标记此点已经记过。

　　　　循环此点的八连通，如果是水，递归循环

　　2. 寻找的次数即为水洼数。

代码：

# include <iostream>

# include <fstream>

using namespace std;

int N, M;

char map[][];

void DFS_Search(int i, int j)

{

    map[i][j] = '.';

    //这样搞定八循环的方式非常棒！！！

    for ( int dx = -; dx <= ; dx++)

    {

        for ( int dy = -; dy <= ; dy++)

        {

            int x = i + dx;

            int y = j + dy;

            if ( x >=  && x <= N && y >=  && y <= M && map[x][y] == 'W')

                DFS_Search(x, y);

        }

    }

}

int main()

{

    int count = ;

//    ifstream cin("Lake_Counting_Data.txt");

    cin>>N>>M;

    for( int i = ; i < N; i++)

    {

        for ( int j = ; j < M; j++)

        {

            cin>>map[i][j];

        }

    }

    for( int i = ; i < N; i++)

    {

        for ( int j = ; j < M; j++)

        {

            if ( map[i][j] == 'W' )

            {

                count++;

                DFS_Search(i, j);

            }

        }

    }

    cout<<count<<endl;

    return ;

}