C++刷leetcode（1162. 地图分析）【广度优先搜索】【图】
题目描述：你现在手里有一份大小为 N x N 的「地图」（网格） grid，上面的每个「区域」（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，请你找出一个海洋区域，这个海洋区域到离它最近的陆地区域的距离是最大的。
我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。
如果我们的地图上只有陆地或者海洋，请返回 -1。
示例 1：
输入：[,,]
输出：2
解释：
海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大，最大距离为 2。
示例 2：
输入：[,,]
输出：4
解释：
海洋区域 (2, 2) 和所有陆地区域之间的距离都达到最大，最大距离为 4。
提示：
1 <= grid.length == grid.length <= 100
grid 不是 0 就是 1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/as-far-from-land-as-possible
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int maxDistance(vector<vector<int>>& grid) {
//广度优先搜索
//构建方向矩阵
vector<vector<int> > direct = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
//构建queue
int len1 = grid.size(), len2 = grid.size();
queue<pair<int, int> > temp;
for(int i = 0; i < len1; i++){
for(int j = 0; j < len2; j++){
if(grid == 1){
temp.push(make_pair(i, j));
grid = 2;
}
}
}
int res = -1;
while(!temp.empty()){
int len = temp.size();
res++;
for(int i = 0; i < len; i++){
pair<int, int> store = temp.front();
temp.pop();
for(auto cha : direct){
int x = store.first + cha;
int y = store.second + cha;
if(x < 0 || y < 0 || x >= len1 || y >= len2 || grid == 2) continue;
grid = 2;
temp.push(make_pair(x, y));
}
}
}
if(res == 0)return -1;
return res;
}
};
参考链接：https://leetcode-cn.com/problems/as-far-from-land-as-possible/solution/jian-dan-java-miao-dong-tu-de-bfs-by-sweetiee/
页:
[1]