読者です 読者をやめる 読者になる 読者になる

川のブログ

川の適当気ままなブログです。 

AOJ 1160 How Many Islands?

こんにちは川です。

今回は、深さ優先探索で解けます。

 

ソースコード

 

#include <bits/stdc++.h>
using namespace std;
bool island[50][50];
int n,m;
int dx[9]={0,1,1,1,0,-1,-1,-1},dy[9]={-1,-1,0,1,1,1,0,-1};
void serch(int y,int x)
{
    island[y][x]=0;
    for(int i=0,ax,ay;i<9;i++)
if((ay=dy[i]+y)<m&&(ax=dx[i]+x)<n&&ay>=0&&ax>=0&&island[ay][ax])
serch(ay,ax);
}
int main() {
    while(cin>>n>>m,n,m){
        int ans=0;
        for(int i=0;i<m;i++)for(int j=0;j<n;j++)cin>>island[i][j];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(island[i][j]){
                    ans++;
                    serch(i,j);
                }
            }
        }
        cout<<ans<<endl;
    }
}