题目：
你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。
请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。
我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
示例 1：
输入：grid = [[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释：
海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。
示例 2：
输入：grid = [[1,0,0],[0,0,0],[0,0,0]]
输出：4
解释：
海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。
提示：
- n == grid.length
- n == grid[i].length
- 1 <= n <= 100
- grid[i][j] 不是 0 就是 1
多源bfs
对于Tree的BFS（典型的「单源 BFS」）大家都比较熟悉：首先把root节点入队，再一层一层无脑遍历就行了。
对于图的BFS（「多源 BFS」）也是一样，与Tree的BFS的区别如下：
-
Tree只有1个root，而图可以有多个源点，所以首先需要把多个源点都入队。
-
Tree是有向的因此不需要标识是否访问过，而对于无向图来说，必须得标志是否访问过哦！并且为了防止某个节点多次入队，需要在其入队之前就将其设置成已访问！
思路：
题目要求先找到离陆地最远的海洋，怎么找到最远的海洋呢？
- 先把所有的陆地都入队
- 然后从各个陆地同时开始一圈一圈的向海洋扩散，
- 那么最后扩散到的海洋就是最远的海洋，并且这个海洋肯定是被离他最近的陆地给扩散到的！
代码：
class Solution {
public:// 四个移动方向int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};int maxDis = -1; int maxDistance(vector<vector<int>>& grid) {int n = grid.size();queue<pair<int, int>> que1;// 将所有陆地加入队列for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){if(grid[i][j] == 1){que1.push({i, j});}}}// 如果没有陆地或没有海洋，返回-1if(que1.empty() || que1.size() == n * n){return -1; }// bfswhile(!que1.empty()){pair<int, int> cur = que1.front(); que1.pop();int curx = cur.first;int cury = cur.second;for(int i = 0; i < 4; i++){int nx = curx + dir[i][0];int ny = cury + dir[i][1];// 检查是否为海洋if(nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 0){grid[nx][ny] = grid[curx][cury] + 1; // 更新距离，同时标记为已访问maxDis = max(maxDis, grid[nx][ny] - 1); // 因为在计算grid[nx][ny] = grid[x][y] + 1时，grid[x][y]本身就是1，多加了1que1.push({nx, ny});}}}return maxDis;}
};
总结：
时间复杂度：O(N^2)，其中 N 是网格的边长。每个单元格最多被访问一次。
空间复杂度：O(N^2)，队列中最多存储所有陆地单元格。
多源bfs需要先把所有的起点都加入队列，同时进行单源bfs，这样重复的路程不再经过，不仅得出的答案正确，而且时间复杂度大大降低，这也就是多源BFS的核心思路，多个起点同时用单源BFS的方法去找最短路径。
参考：
【Leetcode】图的多源BFS详解