在C ++中尽可能远离土地

假设我们有一个N x N网格，仅包含0和1之类的值，其中0代表水，1代表土地，我们必须找到一个水单元，使其与最近的土地单元的距离最大化，并返回该距离。在这里，我们将使用曼哈顿距离-两个像元(x0,y0)和(x1,y1)之间的距离为| x0-x1 | + | y0-y1 |。如果网格中没有土地或水，则返回-1。

然后输出将为2，因为像元(1,1)距距离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：=列数

• 对于i，范围为0至n – 1

• 如果grid [i，j]为1，则将对(i,j)插入q并将m [(i,j)]：=(j,i)

• 对于介于0到n – 1的j

• ret：= -1

• 当q不为空时

• temp：= q的第一个元素，从q删除第一个元素

• 对于0到3范围内的k-

• 将sz减1

• nx：= temp的第一个值+ dir2 [k，0]

• ny：= temp的第二个值+ dir2 [k，1]

• 如果nx和ny不在grid范围内，或者grid [nx，ny]为1，则跳至下一个迭代。

• m [(nx,ny)]：= m [temp]

• ret：=（(nx,ny)和m(temp)的距离）的最大值

• 将(nx,ny)插入q

• 设置grid [nx，ny]：= 1

• sz：= q的大小

• 而sz不为0

• 返回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