数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中尽可能远离陆地
假设我们有一个N x N的网格，其中只包含0和1的值，其中0代表水，1代表陆地，我们需要找到一个水单元，使其到最近陆地单元的距离最大化，并返回该距离。这里我们将使用曼哈顿距离——两个单元(x0, y0)和(x1, y1)之间的距离是|x0 - x1| + |y0 - y1|。如果网格中不存在陆地或水，则返回-1。
| 1 | 0 | 1 |
| 0 | 0 | 0 |
| 1 | 0 | 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
对于j从0到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[nx, ny]为1，则跳过到下一个迭代。
m[(nx, ny)] := m[temp]
ret := (nx, ny)和m[temp]的距离与ret的最大值
将(nx,ny)插入q
设置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
更新于：2020年5月2日
268 次浏览
广告