資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告