The Number of Island

島の数 | Aizu Online Judge

教科書的なDFSの問題なんだが、入力ケースの終わりがちょっと特殊だった。 Patisserie | Aizu Online Judgeを彷彿とさせる。。

bool visited[13][13];
string mp[13];
 
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
 
void solve(int x, int y) {
    visited[x][y]=1;
    for (int i =0; i < 4;i++) {
        int nx=x+dx[i], ny=y+dy[i];
        if (0<=nx&&nx<12&&0<=ny&&ny<12) {
            if (!visited[nx][ny]){
                solve(nx, ny);
            }
        }
    }
}
 
int main() {
    while (1) {
        string s;
        for (int i=0;i<4;i++){
            getline(cin, s);
            if (s!="")break;
        }
        if (s=="")break;
        mp[0]=s;
        for(int i = 0; i < 11; i++) cin >> mp[i+1];
        memset(visited, 0, sizeof(visited));
 
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 12; j++) {
                if (mp[i][j]=='0') {
                    visited[i][j]=1;
                }
            }
        }
        int res=0;
        for(int i=0;i<12;i++) {
            for(int j=0;j<12;j++) {
                if (visited[i][j])continue;
 
                if (mp[i][j]=='1'){
                    solve(i, j);
                    res++;
                }
            }
        }
        cout << res << endl;
    }
    return 0;
}