用 C++ 实现尽可能远离陆地
假设我们有一个 N x N 网格，其中只包含 0 和 1 这样的值，其中 0 代表水，1 代表陆地，我们必须找到一个水单元，使其与最近的陆地单元的距离最大化并返回该距离。这里我们将使用曼哈顿距离减去两个单元 (x0, y0) 和 (x1, y1) 之间的距离为 |x0 - x1| + |y0 - y1|。如果网格中没有陆地或水，则返回 -1。
| 1 | 0 | 1 |
| 0 | 0 | |
| 1 | 0 |
然后输出将为 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 := 列数
for i in range 0 to n – 1
for j in range 0 to n – 1
如果 grid[i, j] 为 1，则将一对 (i, j) 插入 q 并放入 m[(i, j)] := (j ,i)
ret := -1
当 q 不为空时
sz := q 的大小
当 sz 不为 0 时
temp := q 的第一个元素，从 q 中删除第一个元素
对于 k 在 0 到 3 范围内 −
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) 的距离) 和 ret 的最大值
将 (nx,ny) 插入 q
设置 grid[nx, ny] := 1
将 sz 减少 1
return 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
