C++でバイナリ行列内の1に囲まれた0の個数を数えるアルゴリズム

本記事では、バイナリ行列（0と1のみで構成される行列）の中から、1によって完全に囲まれている0の個数を求めるプログラムについて解説します。

具体的には、0と1からなる行列が与えられたとき、行列の外側に到達できない、つまり1に囲まれて閉じ込められている0をすべて見つけ出し、その個数をカウントするのが目的です。

アルゴリズムの考え方

この問題は「境界からたどり着ける0」と「たどり着けない0」を区別することで解決できます。手順は以下のとおりです。

1. 行列の四辺（上端・下端・左端・右端）にある0を起点として、深さ優先探索（DFS）を実行します。
2. DFSで到達できた0はすべて1に書き換え、訪問済みとしてマークします。
3. すべての探索が終わった後、行列に残っている0は境界から到達できなかった、すなわち1に囲まれた0です。その個数を数えて返します。

この方法により、計算量 O(Row × Col) で効率的に答えを求めることができます。

実装例（C++）

#include <iostream>
using namespace std;
#define Row 4
#define Col 5
int r[4] = { 0, 0, 1, -1 };
int c[4] = { 1, -1, 0, 0 };
bool isSafe(int x, int y, int M[][Col]) {
    if (x >= 0 && x <= Row && y >= 0 &&
        y <= Col && M[x][y] == 0)
        return true;
    return false;
}
// 行列に対してDFSを実行
void DFS(int x, int y, int M[][Col]) {
    // 訪問済みとしてマーク
    M[x][y] = 1;
    for (int k = 0; k < 4; k++)
        if (isSafe(x + r[k], y + c[k], M))
            DFS(x + r[k], y + c[k], M);
}
// 1に囲まれた0の個数を返す
int CountAllZero(int M[][Col]){
    for (int i = 0; i < Col; i++)
        if (M[0][i] == 0)
            DFS(0, i, M);
    for (int i = 0; i < Col; i++)
        if (M[Row - 1][i] == 0)
            DFS(Row - 1, i, M);
    for (int i = 0; i < Row; i++)
        if (M[i][0] == 0)
            DFS(i, 0, M);
    for (int i = 0; i < Row; i++)
        if (M[i][Col - 1] == 0)
            DFS(i, Col - 1, M);
// 1に囲まれた残りの0をカウント
int result = 0;
for (int i = 0; i < Row; i++)
    for (int j = 0; j < Col; j++)
        if (M[i][j] == 0)
            result++;
    return result;
}
int main(){
    int M[][Col] = { { 1, 1, 1, 0, 1 },{ 1, 0, 0, 1, 0 },{ 1, 0, 1, 0, 1 },{ 0, 1, 1, 1, 1 } };
    cout << CountAllZero(M) << endl;
    return 0;
}

出力結果

4

コードの解説

まず、isSafe 関数で、指定した座標が行列の範囲内であり、かつそのセルの値が0であるかを判定します。次に、DFS 関数が現在のセルを訪問済み（値を1に変更）とし、上下左右の4方向へ再帰的に探索を進めます。

CountAllZero 関数では、行列の四辺に存在するすべての0からDFSを開始します。これにより、外側とつながっている0はすべて1に書き換えられます。最後に行列全体を走査し、値が0のまま残っているセルを数えれば、それが1に囲まれた0の個数となります。

上記のサンプル行列の場合、境界から到達できない0が4つ存在するため、出力は「4」となります。