C++のバイナリ行列の最も近い1

バイナリ行列が与えられた場合、各セルから1を含む最も近いセルまでの最小距離を見つける必要があります。

例を見てみましょう。

入力

0 0 1
1 1 0
0 0 0

出力

1 1 0 0 0 1 1 1 2

最小距離は、現在のセル行-1セル行+現在のセル列-1セル列から最小の距離です。

アルゴリズム

• 目的のサイズのマトリックスを初期化します。

• 同じサイズの別の行列を初期化して、距離を保存します。

• マトリックス全体を反復処理する

  。

  • 現在のセル値が1の場合、1から1までの距離は0であるため、距離を0に設定します

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

    • マトリックス全体をもう一度繰り返します

    • セルが1の場合、現在のセルからの距離を計算します。

    • 最小距離を更新します。

      。

• 距離行列を印刷します。

実装

以下は、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