C++刷leetcode（1162. 地图分析）【广度优先搜索】【图】

糖逗

题目描述：

1. 你现在手里有一份大小为 N x N 的「地图」（网格） grid，上面的每个「区域」（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，请你找出一个海洋区域，这个海洋区域到离它最近的陆地区域的距离是最大的。
   
2. 
   
3. 我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。
   
4. 
   
5. 如果我们的地图上只有陆地或者海洋，请返回 -1。
   
6. 
   
7.  
   
8. 
   
9. 示例 1：
   
10. 
    
11. 
    
12. 
    
13. 输入：[[1,0,1],[0,0,0],[1,0,1]]
    
14. 输出：2
    
15. 解释：
    
16. 海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大，最大距离为 2。
    
17. 示例 2：
    
18. 
    
19. 
    
20. 
    
21. 输入：[[1,0,0],[0,0,0],[0,0,0]]
    
22. 输出：4
    
23. 解释：
    
24. 海洋区域 (2, 2) 和所有陆地区域之间的距离都达到最大，最大距离为 4。
    
25.  
    
26. 
    
27. 提示：
    
28. 
    
29. 1 <= grid.length == grid[0].length&#160;<= 100
    
30. grid[i][j]&#160;不是&#160;0&#160;就是&#160;1
    
31. 
    
32. 来源：力扣（LeetCode）
    
33. 链接：https://leetcode-cn.com/problems/as-far-from-land-as-possible
    
34. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int maxDistance(vector<vector<int>>& grid) {
   
4.         //广度优先搜索
   
5.         //构建方向矩阵
   
6.         vector<vector<int> > direct = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
   
7.         //构建queue
   
8.         int len1 = grid.size(), len2 = grid[0].size();
   
9.         queue<pair<int, int> > temp;
   
10.         for(int i = 0; i < len1; i++){
    
11.             for(int j = 0; j < len2; j++){
    
12.                 if(grid[i][j] == 1){
    
13.                     temp.push(make_pair(i, j));
    
14.                     grid[i][j] = 2;
    
15.                 }
    
16.             }
    
17.         }
    
18.         int res = -1;
    
19.         while(!temp.empty()){
    
20.             int len = temp.size();
    
21.             res++;
    
22.             for(int i = 0; i < len; i++){
    
23.                 pair<int, int> store = temp.front();
    
24.                 temp.pop();
    
25.                 for(auto cha : direct){
    
26.                     int x = store.first + cha[0];
    
27.                     int y = store.second + cha[1];
    
28.                     if(x < 0 || y < 0 || x >= len1 || y >= len2 || grid[x][y] == 2) continue;
    
29.                     grid[x][y] = 2;
    
30.                     temp.push(make_pair(x, y));
    
31.                 }
    
32.             }
    
33.         }
    
34.         if(res == 0)return -1;
    
35.         return res;
    
36.     }
    
37. };

复制代码

参考链接：https://leetcode-cn.com/problems ... de-bfs-by-sweetiee/