C++の壁と門

1つのmxn 2Dグリッドがあり、それがこれら3つの可能な値で初期化されているとします。

• -壁または障害物の場合は-1。

• ゲートの場合は0。

• INFこれは無限大は空の部屋を意味します。

ここで、2 ^ 31-1 =2147483647はINFです。これは、ゲートまでの距離が2147483647未満であると想定できるためです。空の各部屋に、最も近いゲートまでの距離を入力します。ゲートに到達できない場合は、INFで埋める必要があります。

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

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

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

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

• n：=部屋のサイズ

• m：=（nがゼロ以外の場合は列数、それ以外の場合は0）

• ペアの1つのキューqを定義します

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

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

    • Rooms [i、j]が0と同じ場合、-

      • {i、j}をq

        に挿入します

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

  • sz：=qのサイズ

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

    を実行します。

    • 1つのペアcurrを定義します：=qの最初の要素

    • qから要素を削除

    • x：=curr.first

    • y：=curr.second

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

      • nx：=x + dir [i、0]

      • ny：=y + dir [i、1]

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

        • 次の部分を無視し、次の反復にスキップします

      • Rooms [nx、ny]：=lvl

      • {nx、ny}をq

        に挿入します

例

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

#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:
   void wallsAndGates(vector<vector<int<>& rooms) {
      int n = rooms.size();
      int m = n ? rooms[0].size() : 0;
      queue<pair<int, int> > q;
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < m; j++) {
            if (rooms[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();
            int x = curr.first;
            int y = curr.second;
            for (int i = 0; i < 4; i++) {
               int nx = x + dir[i][0];
               int ny = y + dir[i][1];
               if (nx < 0 || ny < 0 || nx >= n || ny >= m || rooms[nx][ny] < lvl)
                  continue;
               rooms[nx][ny] = lvl;
               q.push({ nx, ny });
            }
         }
      }
   }
};
main(){
   vector<vector<int<> v = {{2147483647,-1,0,2147483647}, {2147483647,2147483647,2147483647,-1}, {2147483647,-1,2147483647,-1}, {0,-1,2147483647,2147483647}};
   Solution ob;
   ob.wallsAndGates(v);
   print_vector(v);
}

入力

{{2147483647,-1,0,2147483647},{2147483647,2147483647,2147483647,-1}, {2147483647,-1,2147483647,-1},{0,-1,2147483647,2147483647}}

出力

[[3, -1, 0, 1, ],[2, 2, 1, -1, ],[1, -1, 2, -1, ],[0, -1, 3, 4, ],]