你现在手里有一份大小为 N x N 的『地图』（网格） grid，上面的每个『区域』（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，你知道距离陆地区域最远的海洋区域是是哪一个吗？请返回该海洋区域到离它最近的陆地区域的距离。
我们这里说的距离是『曼哈顿距离』（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。
如果我们的地图上只有陆地或者海洋，请返回 -1。
示例1：
输入：[[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释：
海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大，最大距离为 2。
示例 2：
输入：[[1,0,0],[0,0,0],[0,0,0]]
输出：4
解释：
海洋区域 (2, 2) 和所有陆地区域之间的距离都达到最大，最大距离为 4。
提示：
1 <= grid.length == grid[0].length <= 100
grid[i][j] 不是 0 就是 1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/as-far-from-land-as-possible
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1.分析题意：题目定义dist<海洋i，陆地>=min(曼哈顿距离<海洋i， 陆地j>)。要求的是max(dist<海洋i，陆地>)。
2.思路：可以想象成从陆地开始向4个方向每轮扩散一格，把海洋变成“陆地”，并记录该区域是第几轮成为“陆地”的，直到图中只有“陆地”为止。所求即为第几轮使所有区域成为“陆地”。
3.算法：图的多源BFS（图的多源BFS可以想象成该图外部有一个“超级源点”，与原来的多个源点都存在一条边，即从“超级源点”开始做单源BFS，原来的多个源点就是BFS的第二层而已）
4.特殊值处理：题目要求如果原始地图上只有陆地或者海洋，返回 -1。
func maxDistance(grid [][]int) int {
// 图的多源广搜，从原始陆地开始，每次扩散一格把海洋变成“陆地”，修改grid[i][j]为扩散轮数+1，直到所有区域变成“陆地”，返回最后一个变成“陆地”的grid[i][j]-1。
queue := make([]int, 0)
// 二维数组的列数（grid为N*N大小，即行数等于列数）
col := len(grid[0])
for i := range grid {
for j := range grid[i] {
// 判断是否是陆地
if grid[i][j] == 1 {
// 陆地加入队列，i == i*col+j/col, j == i*col+j]%col
queue = append(queue, i*col+j)
}
}
}
// 上下左右4个方向进行陆地的扩散
xDir := []int{-1, 0, 1, 0}
yDir := []int{0, -1, 0, 1}
// x ,y 记录当前陆地的两个坐标
x, y := 0, 0
for len(queue) != 0 {
// 从queue[0]中计算出x,y坐标
x, y = queue[0]/col, queue[0]%col
// 队首出队
queue = queue[1:]
// 从该“陆地”开始，往四个方向走一格，看能否扩散
for i := 0; i < 4; i++ {
xMove := xDir[i]+x
yMove := yDir[i]+y
// 如果该区域坐标不越界并且是海洋，就加入队列，并修改该区域的grid[i][j] = 扩散轮数+1(因为原始陆地的grid[i][j]=1,所以是+1)
if xMove >=0 && xMove < col && yMove >= 0 && yMove < col && grid[xMove][yMove] == 0 {
queue = append(queue, xMove*col+yMove)
grid[xMove][yMove] = grid[x][y]+1
}
}
}
// 如果全是陆地或全是海洋，则一次都没有扩散过，保持x=0,y=0
// 如果全是陆地，则grid[x][y] == 1，如果全是海洋，则grid[x][y] == 0
if grid[x][y] == 0 || grid[x][y] == 1 {
// 根据题意，返回-1
return -1
}
// 返回扩散轮数，grid[i][j]记录的是扩散轮数+1
return grid[x][y]-1
}
时间复杂度:O(N2) (遍历二维数组)
空间复杂度:O(N2) （队列最大长度）
原文：https://www.cnblogs.com/nini-skyrim/p/12595629.html