在C ++中尽可能远离土地
假设我们有一个NxN网格，仅包含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