C++で可能な限り土地から遠い

0や1などの値のみを含む1つのNxNグリッドがあり、0は水を表し、1は土地を表すとすると、最も近い土地セルまでの距離が最大になるように水セルを見つけて、距離を返す必要があります。ここでは、マンハッタン距離を使用します。2つのセル（x0、y0）と（x1、y1）の間の距離は| x0--x1|です。 + | y0--y1|。グリッドに土地や水が存在しない場合は、-1を返します。

セル（1,1）は、距離2のすべての土地から可能な限り離れているため、出力は2になります。

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

• dir：=[（1、0）、（-1、0）、（1、-1）、（1、1）、（-1、1）、（-1、-1）、（0、1） 、（0、-1）]

• dir2：=[（1、0）、（-1、0）、（0、1）、（0、-1）]

• マップmを定義します。キューqを定義します。 n：=行数およびc：=列数

• 0からn–1の範囲のiの場合

  • 0からn–1の範囲のjの場合

    • grid [i、j]が1の場合、ペア（i、j）をqに挿入し、m [（i、j）]：=（j、i）

      を配置します。

• ret：=-1

• qが空ではない間

  • sz：=qのサイズ

  • szは0ではありません

    • temp：=qの最初の要素、qから最初の要素を削除

    • 0から3の範囲のkの場合-

      • nx：=temp + dir2 [k、0]

        の最初の値

      • ny：=temp + dir2 [k、1]

        の2番目の値

      • nxとnyがグリッドの範囲内にない場合、またはgrid [nx、ny]が1の場合は、次の反復にスキップします。

      • m [（nx、ny）]：=m [temp]

      • ret：=（（nx、ny）とm（temp）の距離）とretの最大値

      • （nx、ny）をqに挿入します

      • set grid [nx、ny]：=1

    • szを1減らします

• retを返す

例（C ++）

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

#include <bits/stdc++.h>
using namespace std;
int dir[8][2] = {
   {1, 0}, {-1, 0}, {1, -1}, {1, 1},
   {-1, 1}, {-1, -1}, {0, 1}, {0, -1}
};
int dir2[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
   public:
   int calcDist(int x1, int y1, int x2, int y2){
      return abs(x1 - x2) + abs(y1 - y2);
   }
   int maxDistance(vector<vector<int>>& grid) {
      map < pair <int, int>, pair <int, int> > m;
      queue < pair <int, int> > q;
      int n = grid.size();
      int c = n? grid[0].size() : 0;
      for(int i = 0; i < n; i++){
         for(int j = 0; j < c; j++){
            if(grid[i][j] == 1){
               q.push({i, j});
               m[{i, j}] = {i, j};
            }
         }
      }
      int ret = -1;
      while(!q.empty()){
         int sz = q.size();
         while(sz--){
            pair <int, int> temp = q.front();
            q.pop();
            for(int k = 0; k < 4; k++){
               int nx = temp.first + dir2[k][0];
               int ny = temp.second + dir2[k][1];
               if(nx < 0 || ny < 0 || nx >= n || ny >= c || grid[nx][ny]) continue;
               m[{nx, ny}] = m[temp];
               ret = max(calcDist(nx, ny, m[temp].first,
               m[temp].second), ret);
               q.push({nx, ny});
               grid[nx][ny] = 1;
            }
         }
      }
      return ret;
   }
};
main(){
   vector<vector<int>> v1 = {{1,0,1},{0,0,0},{1,0,1}};
   Solution ob;
   cout << (ob.maxDistance(v1));
}

入力

["alice,20,800,mtv","bob,50,1200,mtv"]

出力

2