Re: [閒聊] 每日LeetCode已回收
1162. As Far from Land as Possible
給一個 n*n 的 01 矩陣，
0 代表水池，1 代表陸地，
找到一塊水池距離最近陸地的曼哈頓距離最遠，
若無水池或陸地則回傳 -1。
Example 1:
Input:
101
000
101
Output:
2
Explanation: 正中間的水池離最近的陸地距離為2
Example 2:
Input:
100
000
000
Output:
4
Explanation: 最右下水池離最左上的陸地距離為4
解題思路:
記錄每一格離最近的陸地的距離，原本是陸地的設為0，原本是水池的設為無限大，
將每一個陸地都加入 queue 進行多源 BFS，每次更新上下左右四個位置，
由於是多源同時進行 BFS，距離只會非嚴格遞增，不會有重複更新的問題，
最後看所有距離的最大值，0代表無水池，無限大代表無陸地，兩者皆回傳-1，
其餘數值直接回傳就是答案。
C++ Code:
class Solution {
public:
int maxDistance(vector<vector<int>>& grid) {
queue<pair<int, int>> que;
vector<vector<int>> dis(grid.size(), vector<int>(grid[0].size()));
for(int i = 0; i < grid.size(); i++){
for(int j = 0; j < grid[0].size(); j++){
if(grid[i][j] == 1) que.push({i, j});
else dis[i][j] = INT_MAX;
}
}
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
while(que.size() > 0){
auto front = que.front(); que.pop();
for(int i = 0; i < 4; i++){
int nx = front.first + dx[i];
int ny = front.second + dy[i];
if(nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size()
&& dis[front.first][front.second] + 1 < dis[nx][ny]){
dis[nx][ny] = dis[front.first][front.second] + 1;
que.push({nx, ny});
}
}
}
int ans = 0;
for(auto i : dis){
for(auto j : i){
ans = max(ans, j);
}
}
return (ans == 0 || ans == INT_MAX) ? -1 : ans;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.229.216 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1676015732.A.5FB.html
※ 編輯: idiont (140.113.229.216 臺灣), 02/10/2023 15:56:23
推
02/10 15:59,
2年前
, 1F
02/10 15:59, 1F
→
02/10 16:01,
2年前
, 2F
02/10 16:01, 2F
※ 編輯: idiont (140.113.229.216 臺灣), 02/10/2023 16:02:39
→
02/10 16:12,
2年前
, 3F
02/10 16:12, 3F
→
02/11 02:28,
2年前
, 4F
02/11 02:28, 4F
→
02/11 02:29,
2年前
, 5F
02/11 02:29, 5F
對耶 但想說複雜度一樣就沒特別動了
兩種 special case 也可以在 BFS 前就檢查
寫完今天的 BFS 才看到 然後就懶得改惹
※ 編輯: idiont (140.113.229.216 臺灣), 02/11/2023 08:41:24
討論串 (同標題文章)
完整討論串 (本文為第 227 之 719 篇)：