企业官网建设流程全解析

题目链接：1765. 地图中的最高点

题目解析

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

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

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

具体的步骤：

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

题目给出一个大小为m X n的整数矩阵isWater，它代表了一个由陆地和水域单元格组成的地图，其中：

• 如果isWater[i][j] == 0，坐标为(i, j)的格子是一个陆地格子
• 如果isWater[i][j] == 1，坐标为(i, j)的格子是一个水域格子

我们需要返回一个按照如下规则给每个单元格安排高度后的矩阵：

1. 每个格子的高度都必须是非负的
2. 如果一个格子是水域，那么它的高度必须为0
3. 任意相邻的格子高度差至多为1（当两个格子在上、下、左、右四个方向上互相紧挨着，就称它们为相邻的格子）

返回的矩阵必须使得矩阵中的最高高度值最大。

例1：isWater = [[0,1],[0,0]]

按照规则重新安排高度之后返回的矩阵：[[1,0],[2,1]]

例2：isWater = [[0,0,1],[1,0,0],[0,0,0]]

按照规则重新安排高度之后返回的矩阵：[[1,1,0],[0,1,1],[1,2,2]]

方向向量

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

坐标〖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)找出来，根据规则 2 将其改为0然后标记为已访问
2. 然后以所有的水域单元格(1)为起点，进行多源 BFS 即可（从水域单元格开始向外逐层扩展，在扩展的时候高度都比起始点多1）

由于矩阵中有多个水域单元格 —— 即有多个起点，我们就将所有的起点统一放入队列中，相当于将超级源点放入队列。

层序遍历

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

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

代码实现

classSolution{publicint[][]highestPeak(int[][]isWater){// 初始化intm=isWater.length,n=isWater[0].length;Queue<int[]>queue=newArrayDeque<>();int[]dx={0,0,-1,1};int[]dy={-1,1,0,0};boolean[][]isWaterVisit=newboolean[m][n];// 标记水域// 先将水域改为0并存入队列for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(isWater[i][j]==1){isWater[i][j]=0;isWaterVisit[i][j]=true;queue.offer(newint[]{i,j});}}}// 层序遍历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){// 找到陆地格子,将值改为"位置[row,col]的值+1"if(isWater[x][y]==0&&!isWaterVisit[x][y]){isWater[x][y]=isWater[row][col]+1;queue.offer(newint[]{x,y});}}}}// 返回结果returnisWater;}}

完