AOJ Volume11 1160: How Many Islands

dfsを使用


/********************************************
*   2012/06/18                                *
*    AOJ Volume11 1160                        *
*    How Many Islands?                        *
*********************************************/

//--------------------------------------------------//
//        海->0        陸->1                            //
//--------------------------------------------------//
#include<iostream>

#define MAX_N 50
int field[MAX_N][MAX_N];

/*  w:横  h:縦*/
int w, h;       

void dfs(int x, int y);    //dfs処理用

int main(){
    while(std::cin >> w >> h, w, h){    //地図情報入力
        int result = 0;                 //結果個数初期化
       
        /*地図作成*/
        for(int i=0; i<h; i++)        //縦
            for(int j=0; j<w; j++)    //横
                std::cin >> field[i][j];

        /*島破壊*/
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                if(field[i][j] == 1){
                    /*島があったら*/
                    dfs(j,i);
                    result++;
                }
            }
        }
        std::cout << result << std::endl;//結果出力
    }
    return 0;
}



void dfs(int x, int y){
    int a[8] = {-1, -1, -1, 0, 1, 1, 1, 0};//横
    int b[8] = {-1,  0,  1, 1, 1, 0,-1,-1};//縦

    //今いるところを0にする
    field[y][x] = 0;

    /* 移動する８近傍をループ*/
    for(int i=0; i<8; i++){
        //移動先 (nx, ny)
        int nx = x + a[i], ny = y + b[i];
       
        //移動先が地図上か判定 & 移動先が島かどうか判定
        if( 0<=nx && nx<w && 0<=ny && ny<h && field[ny][nx]==1)
            dfs(nx, ny);
    }
}