你现在手里有一份大小为 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.lengthn == grid[i].length1 <= n <= 100grid[i][j]不是0就是1
解题思路：多源BFS
这道题同样是 542. 01 矩阵 这道题的变形，虽然题目中说曼哈顿距离，需要有两个距离最远的坐标，但其实我们并不需要知道其坐标，只需要知道它的距离即可，为什么呢❓❓❓
其实曼哈顿距离的公式就暗示我们了，两个 x 坐标和两个 y 坐标的距离相加，其实就是在矩阵中两个坐标，只能通过上下左右移动时候走的最短距离！如下图所示：
也就是说这道题其实和 542. 01 矩阵 是一模一样的，我们只需要用一个 distance 表和多源 bfs 来计算出矩阵中 0 和 1 的最远距离即可，这就是最后要求的曼哈顿距离，而不需要说用两个下标去做计算了！
代码几乎是一模一样的，如下所示：
class Solution {
private:
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
public:
int maxDistance(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> distance(m, vector<int>(n, -1)); // 创建并且初始化距离表为-1
// 1. 以1作为源点，将它们都加入队列中，然后修改距离为0
queue<pair<int, int>> bfs;
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
if(grid[i][j] == 1)
{
bfs.push({i, j});
distance[i][j] = 0;
}
}
}
// 2. 进行多源bfs操作，需要一层一层向外拓展
int ret = -1;
while(!bfs.empty())
{
int size = bfs.size();
while(size--)
{
auto [x, y] = bfs.front();
bfs.pop();
for(int i = 0; i < 4; ++i)
{
int newx = x + dx[i], newy = y + dy[i];
if(newx >= 0 && newy >= 0 && newx < m && newy < n && distance[newx][newy] == -1)
{
bfs.push({newx, newy});
distance[newx][newy] = distance[x][y] + 1;
ret = max(ret, distance[newx][newy]); // 别忘了更新最大值
}
}
}
}
return ret; // 如果只有陆地或者海洋的话，那么上面就不会更新ret，就还是-1
}
};