srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

aoj 0067 - The Number of Island

問題

問題概要

nこの数字を使って、合計sにするパターンの総数

解法

dfsで周り4方向と連結した部分を塗りつぶしていく。連結成分を塗り終わると、dfsが終わる。次に、まだ塗り終わっていない場所からdfsを始めて、塗りつぶしていく。これを何回繰り返したかが、cntで答えとなる。bfsでもできるよね。

ミス

教育的

コード

#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
int dy[] = {1, 0, 0, -1};
int dx[] = {0, 1, -1, 0};
vector<string> s(12);

void dfs(int y, int x){
    s[y][x] = '0';
    rep(i, 4){
        int ny = y + dy[i], nx = x + dx[i];
        if(!(0 <= ny && ny < 12 && 0 <= nx && nx < 12)) continue;
        if(s[ny][nx] == '0') continue;
        dfs(ny, nx);
    }
    return;//さらに深く探すことができるない時
}

int main(void){
    while(1){
        int cnt = 0;
        rep(i, 12){
            if(!(cin >> s[i])) return 0;//読み込み失敗した場合
        }

        rep(y, 12)rep(x, 12){
            if(s[y][x] == '1'){
                dfs(y, x);
                cnt++;
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}