AOJ1160 How Many Islands?（精選25）

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1160&lang=jp

グリッド内の島の数を求める問題です。
蟻本にあったLake Counting(POJ 2386）と同じですね。

考察

再帰DFSで書きました。
縦横を間違えがちなので注意して実装しました。

提出コード

#include <bits/stdc++.h>
using namespace std;

int w,h;
int P[50][50];//0 ir 1
int C[50][50];//チェック済判定
int dx[8]={1,-1,0,0,1,1,-1,-1};
int dy[8]={0,0,1,-1,1,-1,1,-1};

void dfs(int x,int y){
  C[x][y]=1;
  for(int i=0;i<8;i++){
    int nx=x+dx[i];
    int ny=y+dy[i];
    //まだ見てない範囲内のところ
    if(0<=nx && nx<h && 0<=ny && ny<w && C[nx][ny]==0){
      C[nx][ny]=1;//見ました
      if(P[nx][ny]==1){
        dfs(nx,ny);
      }
    }
  }
}

int main(){
  while(1){
  cin>>w>>h;    
    if(w==0 && h==0) return 0;
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
        P[i][j]=0;
        C[i][j]=0;
      }
    }
    
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin>>P[i][j];
    }
  }
  int cnt=0;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      //未チェックで島なら島の範囲を判定
      if(C[i][j]==0 && P[i][j]==1){
        cnt++;
        dfs(i,j);
      }
    }
  }
  cout<<cnt<<endl;
  }
}