寝癖頭の解法

勉強中の覚え書きを投稿、更新していきます。

Aizu Online Judge in C++ #Volume11-1160 How Many Islands?

Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。

・問題「島はいくつある?」
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1160&lang=ja
 この問題では,同じ大きさの正方形に区切られたメッシュ状の地図が与えられる.
 この地図は,ある海域を表しており,各正方形の領域が陸または海に対応する.

 陸に対応する二つの正方形領域が,地図上で縦,横または斜め方向に隣接しているなら,一方から他方へ歩いて行くことができる.
 陸に対応する二つの領域が同じ島に属するのは,一方から他方へ(一般には別の陸地を経由して)歩いて行ける時であり,またその時のみである.
 なお,この地図の海域は海で囲まれており,その外側へ歩いて出ることはできない.

 与えられた地図を読み取り,この海域に島がいくつあるか数えるプログラムを作成して欲しい.
 たとえば,図B-1の地図には,全部で三つの島がある.

・入力される値
 入力はデータセットの列であり,各データセットは次のような形式で与えられる.
   w h
   c1,1 c1,2 ... c1,w
   c2,1 c2,2 ... c2,w
   ...
   ch,1 ch,2 ... ch,w
 w と h は地図の幅と高さを表す50以下の正の整数であり,地図は w×h 個の同じ大きさの正方形から構成される.
 w と h の間は空白文字1個で区切られる.

 ci, j は,0 または 1 であり,空白文字1個で区切られる.
 ci, j = 0 なら,地図上で左から i 番目,上か ら j 番目の正方形は海であり,ci, j = 1 なら陸である.
 入力の終わりは,空白文字1個で区切られた2個のゼロのみからなる行で表される.

・期待する出力
 各データセットに対し,島の個数を1行に出力せよ. それ以外の余計な文字を含んではいけない.

僕が作成、提出したコードは、以下のとおりです。

/*
 Volume11-1160 How Many Islands?
 http://judge.u-aizu.ac.jp/
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int w,h;
int a[1000][1000];
int dx[8]={1,1,0,-1,-1,-1,0,1},dy[8]={0,1,1,1,0,-1,-1,-1};
void DFS(int x,int y){
    a[y][x]=0;
    for(int i=0;i<8;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx>=0 && nx<w && ny>=0 && ny<h && a[ny][nx]==1){
            DFS(nx,ny);
        }
    }
}
int main(void){
    int cnt;
    while(1){
        cnt=0;
        cin>>w>>h;
        if(w==0 && h==0){
            return 0;
        }
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                cin>>a[i][j];
            }
        }
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                if(a[i][j]==1){
                    cnt++;
                    DFS(j,i);
                }
            }
        }
        cout<<cnt<<endl;
    }
}

設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/
Volume11-1160 How Many Islands?