AOJ #0067 The Number of Island (島の数)

問題の概要


問題文: AIZU ONLINE JUDGE #0067 The Number of Island (島の数)

f:id:farma_11:20171214142009p:plain
島の例

 0 / 1 で表現される 12 x 12 の領域内に、1つ以上の 1 が隣接して形成されるの数をカウントする問題。 隣接の条件は上下左右いずれかに対して接していることとしている。

解答例


 隣接して構成される領域の数を数える典型的な問題と言える。 深さ優先探索により、全地点を探索し 1 が格納されている数をカウントする。この時、一度探索した部分とその隣接した部分を全て 0 に置き換えることでダブルカウントしてしまうのを防ぐことができる。

 2次元上のグリッド探索については、以下を参考にして欲しい。 farma-11.hatenablog.com

#include <iostream>
using namespace std;

char mp[12][13];  // 12x12の平面図 (mp[][12]は'\0'用)

// 4方位探索用
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
void dfs(int x, int y){
    mp[x][y] = '0';  // 探索済みの部分を '0' に置き換える
    for (int i = 0; i < 4; i++){
        int nx = x + dx[i], ny = y + dy[i];
        if (mp[nx][ny] == '1') dfs(nx, ny);
    }
}

int main() {
    // 平面図の1行目の入力がある限りループをまわす
    while (cin >> mp[0]){
        // 平面図の残り2行目~12行目の入力
        for (int i = 1; i < 12; i++){
            cin >> mp[i];
        }

        int islands = 0; // 島の個数を保持
        // 平面図を(0,0)から順に探索
        for (int x = 0; x < 12; x++){
            for (int y = 0; y < 12; y++){
                // 島を発見したら
                if (mp[x][y] == '1'){
                    islands++;
                    dfs(x, y);
                }
            }
        }
        cout << islands << endl;
    }
}

 以上のソースコードは以下のGithub上にて参照可能です。 github.com

その他の解説サイト