C++のすべての建物からの最短距離

最短距離ですべての建物に到達する空き地に家を作りたいとします。上下左右の4方向しか動かせません。値0、1、または2の2Dグリッドがあります。ここで-

• 0は、自由に通り過ぎることができる空き地を表します。

• 1は私たちが通り抜けることができない建物を表しています。

• 2は私たちが通り抜けることができない障害物を表しています。

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

（0,0）、（0,4）、（2,2）に3つの建物があり、（0,2）に障害物がある場合、ポイント（1,2）は次のようになり、出力は7になります。総移動距離は3+3 + 1 =7であるため、家を建てるのに理想的な空き地です。

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

• ret：=inf

• n：=グリッドの行サイズ

• m：=グリッドの列サイズ

• numberOfOnes：=0

• サイズnxm

  の2D配列distを1つ定義します。

• サイズnxm

  の2D配列リーチを1つ定義します

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

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

    • grid [i、j]が1と同じ場合、-

      • （numberOfOnesを1つ増やします）

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

      • {i、j}をqに挿入

      • 訪問した1セットを定義する

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

        • sz：=qのサイズ

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

          を実行します。

          • curr：=qの最初の要素

          • qから要素を削除

          • x：=curr.first

          • y：=curr.second

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

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

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

            • nxとnyがグリッドの範囲内にある場合orgrid[nx、ny]が0でない場合、

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

            • {nx、ny}をvisited

              に挿入します

            • dist [nx、ny]：=dist [nx、ny] + lvl

            • （reach [nx、ny]を1増やします）

            • {nx、ny}をq

              に挿入します

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

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

    • grid [i、j]が0と同じで、reach [i、j]がnumberOfOnesと同じ場合、-

      • ret：=retとdist[i、j]

        の最小値

• return（retがinfと同じ場合は-1、それ以外の場合はret）

例

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

int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
   int shortestDistance(vector<vector<int>>& grid) {
      int ret = INT_MAX;
      int n = grid.size();
      int m = grid[0].size();
      int numberOfOnes = 0;
      vector < vector <int> > dist(n, vector <int>(m));
      vector < vector <int> > reach(n, vector <int>(m));
      for(int i = 0; i < n; i++){
         for(int j = 0; j < m; j++){
            if(grid[i][j] == 1){
               numberOfOnes++;
               queue < pair <int, int> > q;
               q.push({i, j});
               set < pair <int, int> > visited;
               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 k = 0; k < 4; k++){
                        int nx = x + dir[k][0];
                        int ny = y + dir[k][1];
                        if(nx < 0 || ny < 0 || nx >= n || ny >= m || visited.count({nx, ny}) || grid[nx][ny] != 0) continue;
                        visited.insert({nx, ny});
                        dist[nx][ny] += lvl;
                        reach[nx][ny]++;
                        q.push({nx, ny});
                     }
                  }
               }
            }
         }
      }
      for(int i = 0; i < n; i++){
         for(int j = 0; j < m; j++){
            if(grid[i][j] == 0 && reach[i][j] == numberOfOnes){
               ret = min(ret, dist[i][j]);
            }
         }
      }
      return ret == INT_MAX ? -1 : ret;
   }
};

入力

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

出力

7