POJ_No.2386: Lake Counting

dfs。

/********************************************************************************************
*    2012/04/24                                                                                *
*    プログラミングコンテストちゃれんじブック                                                *
*    p.35 第二章 2-1すべての基本"全探索"                                                        *
*    Lake Conting (POJ NO.2386)                                                                *
*    大きさがN×Mの庭がある。そこに雨が降り、水溜りができた。水溜りは８近傍で隣接している    *
*    場合につながっているとみなす。全部でいくつの水溜りがあるか                                *
*                                                                                            *
*            8近傍***                                                                        *
*                    *w*                                                                        *
*                    ***                                                                        *
*    適当なWからはじめ、そこからつながっている部分を[.]に置き換えるという操作を繰り返す。    *
*    1回のDFSで、はじめのWとつながっているWはすべて[.]に置き換わるため、Wがなくなるまで何回    *
*    DFSを行ったかが答えになる。状態の遷移は8方向の移動の8通りで、DFSは各マスに対してたかだ  *
*    1回しか呼び出されないため、計算量はO(8×N×M)=O(N×M)となる。                            *
*                                                                                            *
*    crane                                                                                *
********************************************************************************************/

/**************************************************
**************!制約!*******************************
***************・N,M≦100**************************
**************************************************/

#include<iostream>

void dfs(int x, int y);    //[w] -> [.]

int N,M;        //縦×横 サイズ
char **field;    //庭

int main(){
    int res=0; //結果

    //庭の大きさ(入力)
    std::cin >>    N >> M;
    /*多次元配列確保*/
    field = new char*[N];
    for(int i=0; i<M; i++){
        field[i] = new char[M];
    }
    //庭作成
    for(int i=0; i<N;i++){
        for(int j=0; j<M; j++){
            std::cin>> field[i][j];
        }
    }

    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(field[i][j] == 'W'){
                //Wが残っているならそこからdfsをはじめる
                dfs(i, j);
                res++;
            }
        }
    }
    //結果出力
    std::cout << res << std::endl;
    int ff;
    std::cin >> ff;
    return 0;
}

void dfs(int x, int y){
    //今いるところを.に置き換える
    field[x][y] = '.';

    //移動する8方向をループ
    for(int dx=-1; dx<=1; dx++){
        for(int dy=-1; dy<=1; dy++){
            //x方向にdy y方向にdy移動した場所を(nx,ny)とする
            int nx = x + dx, ny = y + dy;

            //nxとnyが庭の範囲内かどうかとfield[nx][ny]が水溜りかどうかを判定
            if(0 <= nx && ny < N && 0 < ny && ny < M && field[nx][ny] == 'W')    dfs(nx, ny);
        }
    }
}