C++でバイナリ行列の各セルから最も近い1までの距離を求める方法

バイナリ行列（0と1だけで構成された行列）が与えられたとき、各セルから最も近い「1」のセルまでの最小距離を求める問題について解説します。

ここでの距離はマンハッタン距離、すなわち「行の差の絶対値 ＋ 列の差の絶対値」として定義されます。

入力例と出力例

入力

0 0 1
1 1 0
0 0 0

出力

1 1 0
0 0 1
1 1 2

この出力は、行列内のすべてのセルについて、そのセルから最も近い「1」までの距離を表しています。元々「1」であるセルの距離は当然 0 になります。

アルゴリズム

基本となるアプローチは全探索（ブルートフォース）です。手順は以下の通りです。

• 指定したサイズの入力行列を初期化します。

• 同じサイズの距離格納用行列を別途用意し、大きな値（INT_MAX）で初期化します。

• 行列全体を走査します。

  • 現在のセルの値が 1 の場合：1 から 1 への距離は 0 なので、そのセルの距離を 0 に設定します。

  • 現在のセルの値が 0 の場合：

    • 再度行列全体を走査します。

    • 走査先のセルが 1 であれば、現在のセルからの距離を計算します。

    • これまでの最小距離より小さければ、最小距離を更新します。

• 最後に距離行列を出力します。

C++での実装

以下は、上記のアルゴリズムをC++で実装したコードです。

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> findNearest1Distance(vector<vector<int>>& matrix) {
    int rows = matrix.size();
    if (rows == 0) {
        return matrix;
    }
    int cols = matrix[0].size();
    vector<vector<int>> distance(rows, vector<int>(cols, INT_MAX));
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (matrix[i][j] == 1) {
                distance[i][j] = 0;
            } else if (matrix[i][j] == 0) {
                for (int k = 0; k < rows; k++) {
                    for (int l = 0; l < cols; l++) {
                        if (matrix[k][l] == 1) {
                            distance[i][j] = min(distance[i][j], abs(k - i) + abs(l - j));
                        }
                    }
                }
            }
        }
    }
    return distance;
}

int main() {
    vector<vector<int>> matrix{
        {0, 0, 1},
        {1, 1, 0},
        {0, 0, 0}
    };
    vector<vector<int>> result = findNearest1Distance(matrix);
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cout << result[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

1 1 0
0 0 1
1 1 2

計算量と改善のヒント

この全探索アプローチでは、各セルごとに行列全体を再走査するため、時間計算量は O(行数² × 列数²) となります。行列が大きくなると処理が非常に遅くなる点に注意が必要です。

より効率的にしたい場合は、マルチソースBFS（幅優先探索）の活用を検討しましょう。すべての「1」のセルをあらかじめキューに入れておき、BFSを一度だけ実行することで、全セルの最短距離を O(行数 × 列数) で求められます。大規模な入力を扱う場合や競技プログラミングでは、こちらの手法が標準的な解法となります。