文章目录题目解析方向向量算法原理细节问题层序遍历代码实现题目链接1162. 地图分析题目解析多源点最短路问题指的是多个单源点最短路问题。对于单源点最短路问题是只有一个起点和一个终点的而对于多源点最短路问题是有多个起点和一个终点。而多源 BFS则指的是用 BFS 解决边权为 1 的多源点最短路问题。对于这类问题通常是将所有起点看作一个“超级源点”然后问题就变成只有一个起点(超级源点) 和一个终点的单源点最短路问题了。然后使用一次 BFS 即可解决问题。具体的步骤先将所有的起点加入队列中等同于将超级源点加入队列逐层往外扩展题目给出一个大小n x n的网格grid上面的每个单元格都用0和1标记0代表海洋1代表陆地。我们需要找出一个海洋单元格该单元格离它最近陆地单元格的距离最大然后返回这个最大的距离。如果网格上只有陆地或者海洋就返回-1。这里的距离指的是曼哈顿距离举例点x1y1和点x2y2的距离为|x1 - x2| |y1 - y2|例1grid [[1,0,1],[0,0,0],[1,0,1]]101000101dist 矩阵010121010输出2例2grid [[1,0,0],[0,0,0],[0,0,0]]100000000dist 矩阵012123234输出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)并将其在dist 距离矩阵中的对应值改为0并放入队列然后以dist 距离矩阵中的陆地(0)为起点进行 多源 BFS 即可从起点开始逐层扩展并将扩展后的值也放入队列在层序遍历的时候边扩展边记录最大的距离值返回结果细节问题我们对于最终返回的距离矩阵dist做以下操作初始化其所有值为 -1表示该位置未被访问过若某位置的值不为 -1 则说明已被访问过每一个位置的值不为 -1都表示最短距离同时也是扩展的层数在层序遍历的时候只需要通过当前位置在距离数组中对应位置的值再1就可以实现结果的更新层序遍历我们使用一个队列实现层序遍历的操作队列存储起始位置和与其上下左右相邻位置的坐标当队列不为空时一直取出队首元素获取坐标然后根据坐标向该元素的上下左右四个方向访问查找符合条件的方格坐标合法且未被访问过找到符合条件的方格之后从距离矩阵dist中取出与队首元素坐标对应位置的值再1然后将值存入当前访问位置在距离矩阵dist中的对应位置再将这个值放入队列当队列为空层序遍历完毕代码实现classSolution{publicintmaxDistance(int[][]grid){// 初始化intmgrid.length,ngrid[0].length;Queueint[]queuenewArrayDeque();int[]dx{0,0,-1,1};int[]dy{-1,1,0,0};int[][]distnewint[m][n];for(int[]arr:dist){Arrays.fill(arr,-1);// 将dist矩阵中的值初始化为-1,表示未被访问过}// 先遍历矩阵找到陆地for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]1){dist[i][j]0;// 将距离矩阵中对应位置的值设置为0queue.offer(newint[]{i,j});// 放入队列}}}// 层序遍历intmaxDist-1;while(!queue.isEmpty()){int[]topqueue.poll();introwtop[0],coltop[1];for(intk0;k4;k){intxrowdx[k],ycoldy[k];if(x0xmy0yndist[x][y]-1){dist[x][y]dist[row][col]1;queue.offer(newint[]{x,y});maxDistMath.max(maxDist,dist[x][y]);}}}// 返回结果returnmaxDist;}}完