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;
}
};