文章目录题目解析方向向量算法原理层序遍历代码实现题目链接1765. 地图中的最高点题目解析多源点最短路问题指的是多个单源点最短路问题。对于单源点最短路问题是只有一个起点和一个终点的而对于多源点最短路问题是有多个起点和一个终点。而多源 BFS则指的是用 BFS 解决边权为 1 的多源点最短路问题。对于这类问题通常是将所有起点看作一个“超级源点”然后问题就变成只有一个起点(超级源点) 和一个终点的单源点最短路问题了。然后使用一次 BFS 即可解决问题。具体的步骤先将所有的起点加入队列中等同于将超级源点加入队列逐层往外扩展题目给出一个大小为m X n的整数矩阵isWater它代表了一个由陆地和水域单元格组成的地图其中如果isWater[i][j] 0坐标为(i, j)的格子是一个陆地格子如果isWater[i][j] 1坐标为(i, j)的格子是一个水域格子我们需要返回一个按照如下规则给每个单元格安排高度后的矩阵每个格子的高度都必须是非负的如果一个格子是水域那么它的高度必须为0任意相邻的格子高度差至多为1当两个格子在上、下、左、右四个方向上互相紧挨着就称它们为相邻的格子返回的矩阵必须使得矩阵中的最高高度值最大。例1isWater [[0,1],[0,0]]0100按照规则重新安排高度之后返回的矩阵[[1,0],[2,1]]1021例2isWater [[0,0,1],[1,0,0],[0,0,0]]001100000按照规则重新安排高度之后返回的矩阵[[1,1,0],[0,1,1],[1,2,2]]110011122方向向量在继续之前有必要知道我们在解决矩阵搜索类问题时访问某位置上下左右四个方向的操作。坐标〖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)找出来根据规则 2 将其改为0然后标记为已访问然后以所有的水域单元格(1)为起点进行多源 BFS 即可从水域单元格开始向外逐层扩展在扩展的时候高度都比起始点多1由于矩阵中有多个水域单元格 —— 即有多个起点我们就将所有的起点统一放入队列中相当于将超级源点放入队列。层序遍历我们使用一个队列实现层序遍历的操作队列存储起始位置和与其上下左右相邻位置的坐标当队列不为空时一直取出队首元素获取坐标然后根据坐标向该元素的上下左右四个方向访问查找符合条件的方格坐标合法且未被访问过找到符合条件的方格之后从矩阵isWater中取出与队首元素坐标对应位置的值再1然后将值存入当前访问位置在矩阵isWater中的对应位置再将这个值放入队列当队列为空层序遍历完毕代码实现classSolution{publicint[][]highestPeak(int[][]isWater){// 初始化intmisWater.length,nisWater[0].length;Queueint[]queuenewArrayDeque();int[]dx{0,0,-1,1};int[]dy{-1,1,0,0};boolean[][]isWaterVisitnewboolean[m][n];// 标记水域// 先将水域改为0并存入队列for(inti0;im;i){for(intj0;jn;j){if(isWater[i][j]1){isWater[i][j]0;isWaterVisit[i][j]true;queue.offer(newint[]{i,j});}}}// 层序遍历while(!queue.isEmpty()){int[]topqueue.poll();introwtop[0],coltop[1];for(intk0;k4;k){intxrowdx[k],ycoldy[k];if(x0xmy0yn){// 找到陆地格子,将值改为位置[row,col]的值1if(isWater[x][y]0!isWaterVisit[x][y]){isWater[x][y]isWater[row][col]1;queue.offer(newint[]{x,y});}}}}// 返回结果returnisWater;}}完