一、题目描述
二、算法原理
思路：使用多源 BFS 算法
1）先创建一个二维数组来统计距离，再标记陆地的距离为 0，此时把陆地的坐标入队列
2）使用 BFS 算法统计陆地到上下左右的海洋的距离：
3）此时当队列为空时，此时当前坐标的值就是陆地到海洋的最大距离；
三、代码实现
class Solution { int dx[4] = {0,0,-1,1}; int dy[4] = {1,-1,0,0}; typedef pair<int,int> PII; public: int maxDistance(vector<vector<int>>& grid) { //使用多源 BFS int n = grid.size(),m = grid[0].size(); vector<vector<int>> vis(n,vector<int>(m,-1));//统计陆地到海洋的距离 queue<PII> que; for(int i = 0; i < n; i++)//标记陆地的距离为0 { for(int j = 0; j < m; j++) { if(grid[i][j] == 1) { vis[i][j] = 0; que.push({i,j});//让陆地的坐标入队列 } } } while(que.size())//BFS { auto [x,y] = que.front(); que.pop(); for(int i = 0; i < 4; i++) { int a = x + dx[i]; int b = y + dy[i]; if(a >= 0 && b >= 0 && a < n && b < m && vis[a][b] == -1 && grid[a][b] == 0) { vis[a][b] = vis[x][y] + 1; que.push({a,b}); } } if(que.empty() && vis[x][y]) return vis[x][y];//陆地到海洋的最大距离 } return -1; } };
