企业官网建设流程全解析

题目链接：1162. 地图分析

题目解析

多源点最短路问题指的是多个单源点最短路问题。对于单源点最短路问题，是只有一个起点和一个终点的，而对于多源点最短路问题，是有多个起点和一个终点。而多源 BFS则指的是用 BFS 解决边权为 1 的多源点最短路问题。

对于这类问题，通常是将所有起点看作一个“超级源点”，然后问题就变成只有一个起点(超级源点) 和一个终点的单源点最短路问题了。

然后使用一次 BFS 即可解决问题。

具体的步骤：

1. 先将所有的起点加入队列中（等同于将超级源点加入队列）
2. 逐层往外扩展

题目给出一个大小n x n的网格grid，上面的每个单元格都用0和1标记，0代表海洋，1代表陆地。

我们需要找出一个海洋单元格，该单元格离它最近陆地单元格的距离最大，然后返回这个最大的距离。如果网格上只有陆地或者海洋，就返回-1。

这里的距离指的是曼哈顿距离，举例：点（x1，y1）和点（x2，y2）的距离为|x1 - x2| + |y1 - y2|

例1，grid = [[1,0,1],[0,0,0],[1,0,1]]

dist 矩阵：

输出：2

例2，grid = [[1,0,0],[0,0,0],[0,0,0]]

dist 矩阵：

输出：4

方向向量

在继续之前，有必要知道我们在解决矩阵搜索类问题时访问某位置上下左右四个方向的操作。

坐标〖i, j〗的上下左右四个坐标是在i和j加上了 0、1、-1 ：

• 上下坐标：〖i + (-1), j + 0〗和〖i + 1, j + 0〗；
• 左右坐标：〖i + 0, j + (-1)〗和〖i + 0, j + 1〗。

因此需要定义两个向量坐标：dx = {0, 0, -1, 1}，dy = {-1, 1, 0, 0}。

在需要访问时，通过 〖row, col〗坐标和四次循环依次访问即可。

算法原理

本题从陆地入手：

1. 先遍历原矩阵，找到陆地(1)并将其在dist 距离矩阵中的对应值改为0并放入队列
2. 然后以dist 距离矩阵中的陆地(0)为起点，进行 多源 BFS 即可（从起点开始逐层扩展，并将扩展后的值也放入队列），在层序遍历的时候边扩展边记录最大的距离值
3. 返回结果

细节问题

我们对于最终返回的距离矩阵dist做以下操作：

1. 初始化其所有值为 -1，表示该位置未被访问过，若某位置的值不为 -1 则说明已被访问过
2. 每一个位置的值（不为 -1）都表示最短距离，同时也是扩展的层数，在层序遍历的时候只需要通过当前位置在距离数组中对应位置的值再+1就可以实现结果的更新

层序遍历

我们使用一个队列实现层序遍历的操作：

1. 队列存储起始位置和与其上下左右相邻位置的坐标
2. 当队列不为空时，一直取出队首元素获取坐标，然后根据坐标向该元素的上下左右四个方向访问查找符合条件的方格（坐标合法且未被访问过）
3. 找到符合条件的方格之后，从距离矩阵dist中取出与队首元素坐标对应位置的值再+1，然后将值存入当前访问位置在距离矩阵dist中的对应位置，再将这个值放入队列
4. 当队列为空，层序遍历完毕

代码实现

classSolution{publicintmaxDistance(int[][]grid){// 初始化intm=grid.length,n=grid[0].length;Queue<int[]>queue=newArrayDeque<>();int[]dx={0,0,-1,1};int[]dy={-1,1,0,0};int[][]dist=newint[m][n];for(int[]arr:dist){Arrays.fill(arr,-1);// 将dist矩阵中的值初始化为-1,表示未被访问过}// 先遍历矩阵找到陆地for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(grid[i][j]==1){dist[i][j]=0;// 将距离矩阵中对应位置的值设置为0queue.offer(newint[]{i,j});// 放入队列}}}// 层序遍历intmaxDist=-1;while(!queue.isEmpty()){int[]top=queue.poll();introw=top[0],col=top[1];for(intk=0;k<4;k++){intx=row+dx[k],y=col+dy[k];if(x>=0&&x<m&&y>=0&&y<n&&dist[x][y]==-1){dist[x][y]=dist[row][col]+1;queue.offer(newint[]{x,y});maxDist=Math.max(maxDist,dist[x][y]);}}}// 返回结果returnmaxDist;}}

完