【016·暴力解】1765. 地图中的最高点【多源BFS】

地图中的最高点给你一个大小为 m x n 的整数矩阵 isWater 它代表了一个由 陆地 和 水域 单元格组成的地图。如果 isWater[i][j] 0 格子 (i, j) 是一个 陆地 格子。如果 isWater[i][j] 1 格子 (i,j) 是一个 水域 格子。你需要按照如下规则给每个单元格安排高度每个格子的高度都必须是非负的。如果一个格子是 水域那么它的高度必须为 0 。任意相邻的格子高度差 至多 为 1。当两个格子在正东、南、西、北方向上相互紧挨着就称它们为相邻的格子。也就是说它们有一条公共边找到一种安排高度的方案使得矩阵中的最高高度值 最大 。 请你返回一个大小为 m x n 的整数矩阵 height 其中height[i][j] 是格子 (i, j) 的高度。如果有多种解法请返回 任意一个 。https://leetcode.cn/problems/map-of-highest-peak/多源BFS水源索引入队陆地赋值-1表示未处理过已处理过必定大于-1BFS层次遍历下一层次数值当前层次数值1/* * Copyright (c) Huawei Technologies Co., Ltd. 2023-2023. All rights reserved. */packagecom.huawei.prac;importjava.util.ArrayDeque;importjava.util.Arrays;importjava.util.Queue;classSolutionRd{publicstaticvoidmain(String[]args){int[][]isWaternewint[][]{{0,0,1},{1,0,0},{0,0,0}};for(int[]arr:isWater){Arrays.stream(arr).forEach(System.out::print);System.out.println();}System.out.println();int[][]resArrhighestPeak(isWater);for(int[]arr:resArr){Arrays.stream(arr).forEach(System.out::print);System.out.println();}}/** * 765. 地图中的最高点[多源BFS] * 时间复杂度n方执行时间缩短 97.3% 1900ms - 50ms * * param isWater 陆地水域地图二维数组 * return 高度矩阵使得矩阵中的最高高度值 最大 */publicstaticint[][]highestPeak(int[][]isWater){Queueint[]queuenewArrayDeque();int[][]resArrnewint[isWater.length][isWater[0].length];// 上 下 左 右 移动int[][]direcnewint[][]{{-1,0},{1,0},{0,-1},{0,1}};// 水源入队陆地赋值-1for(inti0;iisWater.length;i){for(intj0;jisWater[0].length;j){if(isWater[i][j]1){queue.offer(newint[]{i,j});}else{resArr[i][j]-1;}}}// BFSwhile(!queue.isEmpty()){int[]arrqueue.poll();for(int[]ints:direc){introwNextarr[0]ints[0];intcolNextarr[1]ints[1];if(invalid(rowNext,colNext,resArr)){continue;}resArr[rowNext][colNext]resArr[arr[0]][arr[1]]1;queue.offer(newint[]{rowNext,colNext});}}returnresArr;}privatestaticbooleaninvalid(introwNext,intcolNext,int[][]arr){returnrowNextarr.length||rowNext0||colNextarr[0].length||colNext0||arr[rowNext][colNext]!-1;}}