01C++のマトリックス

0と1で構成される行列があるとすると、各セルの最も近い0の距離を見つける必要があります。ここで、2つの隣接するセル間の距離は1です。

したがって、入力が次のような場合

その場合、出力は次のようになります

これを解決するには、次の手順に従います-

• サイズの配列ディレクトリを定義します：4 x 2：={{1、0}、{-1、0}、{0、-1}、{0、1}}

• n：=行数、m：=列数

• 次数（n x m）の1つの行列retを定義し、これをinfで埋めます

• 1つのキューを定義するq

• 初期化i：=0の場合、i

  • 初期化j：=0の場合、j

    • 行列[i、j]がゼロ以外の場合、-

      • ret [i、j]：=0

      • {i、j}をqに挿入

• 初期化レベル：=1の場合、qが空でない場合は、更新（レベルを1増やします）、実行-

  • sz：=qのサイズ

  • szがゼロ以外の場合、反復ごとにszを1ずつ減らし、-

    を実行します。

    • 1つのペアcurrを定義します：=qのフロント要素

    • qから要素を削除

    • 初期化k：=0の場合、k <4の場合、更新（kを1増やします）、実行-

      • nx：=curr.first + dir [k、0]

      • ny：=curr.second + dir [k、1]

      • nx<0またはnx>=nまたはny<0またはny>=mまたはret[nx、ny]

        • ret [nx、ny]：=lvl

      • {nx、ny}をq

        に挿入します

• retを返す

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
class Solution {
public:
   vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
   int n = matrix.size();
   int m = matrix[0].size();
   vector < vector <int> > ret(n, vector <int>(m, INT_MAX));
   queue < pair <int, int> > q;
   for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
         if(!matrix[i][j]){
            ret[i][j] = 0;
            q.push({i, j});
         }
      }
   }
   for(int lvl = 1; !q.empty(); lvl++){
      int sz = q.size();
      while(sz--){
         pair <int, int> curr = q.front();
         q.pop();
         for(int k = 0; k < 4; k++){
            int nx = curr.first + dir[k][0];
            int ny = curr.second + dir[k][1];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m || ret[nx][ny] < lvl) continue;
               ret[nx][ny] = lvl;
               q.push({nx, ny});
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,0,0},{0,1,0},{1,1,1}};
   print_vector(ob.updateMatrix(v));
}

入力

{{0,0,0},{0,1,0},{1,1,1}}

出力

[[0, 0, 0, ],[0, 1, 0, ],[1, 2, 1, ],]