衡阳企业网站建设,开发平台 华为,小程序商店图标,唐山快速建站的公司文章目录1. 题目2. 解题1. 题目
给你一个大小为 m x n 的整数矩阵 isWater #xff0c;它代表了一个由 陆地 和 水域 单元格组成的地图。
如果 isWater[i][j] 0 #xff0c;格子 (i, j) 是一个 陆地 格子。 如果 isWater[i][j] 1 #xff0c;格子 (i, j) 是一个 水域 格…
文章目录1. 题目2. 解题1. 题目
给你一个大小为 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) 的高度。如果有多种解法请返回 任意一个 。
示例 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]]
解释所有安排方案中最高可行高度为 2 。
任意安排方案中只要最高高度为 2 且符合上述规则的都为可行方案。提示
m isWater.length
n isWater[i].length
1 m, n 1000
isWater[i][j] 要么是 0 要么是 1 。
至少有 1 个水域格子。来源力扣LeetCode 链接https://leetcode-cn.com/problems/map-of-highest-peak 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
广度优先搜索即可先把水域加入队列
class Solution {
public:vectorvectorint highestPeak(vectorvectorint isWater) {int m isWater.size(), n isWater[0].size();queuepairint,int q;vectorvectorbool vis(m, vectorbool(n, false));for(int i 0; i m; i) {for(int j 0; j n; j)if(isWater[i][j]) // 是水{q.push({i,j});vis[i][j] true;}}vectorvectorint dir {{1,0},{0,1},{-1, 0},{0,-1}};int h 0;while(!q.empty()){int size q.size();while(size--){pairint,int t q.front();q.pop();isWater[t.first][t.second] h;for(int k 0; k 4; k){int x t.firstdir[k][0];int y t.seconddir[k][1];if(x0 x m y0 y n !vis[x][y]){q.push({x,y});vis[x][y] true;}}}h;}return isWater;}
};464 ms 106.4 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
