题目描述：
你现在手里有一份大小为 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）开始，要扩散多少次，才能把所有的海洋给覆盖掉。「最远」应该从这个角度来理解。
而「该海洋区域到离它最近的陆地区域的距离」，「最近」是因为一定是距离这个最后才扩散到的海洋的最近的陆地才能扩散到它。
分析：
二维表格上的问题，常用的算法是深度优先遍历、广度优先遍历和并查集，由于这里计算的结果和距离相关，显然使用广度优先遍历；
但是题目问的是「距离陆地区域最远的海洋区域」，这和我们的经验稍微有点出入。一般而言，「广度优先遍历」求的是最短路径，但仔细一想，发现其实广度优先遍历也是适用的：
求最短路径的时候，只要找到目标值，返回即可；
求最长路径的时候，所有目标值都看完以后，才返回。
这道题「广度优先遍历」的起点有多个，但完全不影响算法的正确性，可以假想一个虚拟的起点，初始的起点就是由虚拟起点扩散开来的，示意图可以参考 题解 ，特别形象。
这里题目中介绍的「曼哈顿距离」，其实就是对广度优先遍历（BFS）逐层向外扩散的精准数学解释，每扩散一次，曼哈顿距离就加 1。
编写广度优先遍历算法的注意事项：
如果题目要求返回的结果和距离相关，需要在 while 循环内部一下子把当前列表的所有元素都依次取出来，这种「一下子」操作的次数就是我们需要的距离；
如果一个单元格被添加到队列以后，需要马上将它标记为已经访问（根据情况，可以直接在原始输入数组上修改，也可以使用一个布尔数组 visited 进行标记），如果不这么做，很可能会出现死循环，这一点如果一开始没有注意到，也可以通过调试代码观察出。
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
public int maxDistance(int[][] grid) {
// 方向向量int[][] directions = {
{
1, 0}, {
-1, 0}, {
0, 1}, {
0, -1}};// 由于题目中给出了 grid 的范围，因此不用做输入检查int N = grid.length;Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (grid[i][j] == 1) {
queue.add(getIndex(i, j, N));}}}int size = queue.size();if (size == 0 || size == N * N) {
return -1;}int step = 0;while (!queue.isEmpty()) {
int currentQueueSize = queue.size();for (int i = 0; i < currentQueueSize; i++) {
Integer head = queue.poll();int currentX = head / N;int currentY = head % N;for (int[] direction : directions) {
int newX = currentX + direction[0];int newY = currentY + direction[1];// 只关心有效范围内的海洋（0）if (inArea(newX, newY, N) && grid[newX][newY] == 0) {
// 赋值成为一个不等于 0 的整数均可，因为后续逻辑只关心海洋（0）grid[newX][newY] = 1;queue.add(getIndex(newX, newY, N));}}}step++;}// 由于最后一步，没有可以扩散的的区域，但是 step 加了 1，故在退出循环的时候应该减 1return step - 1;}/*** @param x 二维表格单元格横坐标* @param y 二维表格单元格纵坐标* @param cols 二维表格列数* @return*/private int getIndex(int x, int y, int cols) {
return x * cols + y;}/*** @param x 二维表格单元格横坐标* @param y 二维表格单元格纵坐标* @param N 二维表格行数（列数）* @return 是否在二维表格有效范围内*/private boolean inArea(int x, int y, int N) {
return 0 <= x && x < N && 0 <= y && y < N;}public static void main(String[] args) {
// int[][] grid = {
{1, 0, 1}, {0, 0, 0}, {1, 0, 1}};int[][] grid = {
{
1, 0, 0}, {
0, 0, 0}, {
0, 0, 0}};Solution solution = new Solution();int res = solution.maxDistance(grid);System.out.println(res);}
}