首页 > 分享 > 3, y: 5, i: 3, j: 3, direction: '

3, y: 5, i: 3, j: 3, direction: '

花匠小妙招
2024-09-16 04:25

1765. 地图中的最高点（2022-1-29）

给你一个大小为 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：

示例1

输入：isWater = [[0,1],[0,0]]
输出：[[1,0],[2,1]]
解释：上图展示了给各个格子安排的高度。
蓝色格子是水域格，绿色格子是陆地格。

示例 2：

示例2

输入：isWater = [[0,0,1],[1,0,0],[0,0,0]]
输出：[[1,1,0],[0,1,1],[1,2,2]]
解释：所有安排方案中，最高可行高度为 2 。
任意安排方案中，只要最高高度为 2 且符合上述规则的，都为可行方案。

解题思路

虽然只是个中等难度的题，但是这种广度优先搜索的算法（bfs）已经见到很多次了，每次都是似懂非懂的看着别人的代码敲出了AC，虽然懂得大体思路，但不清楚怎么具体实现。

这次不一样了，已经可以自己写出来，对搜索的过程也有自己的感悟了。

写一个方向数组directions保存上下左右的移动，具体顺序无所谓，就是得有。然后在每一个队列中的点需要移动的时候，去遍历这个方向数组，就可以了。其实这里是用到了策略模式的设计方法。

之后就是把源点找出来并推入到队列中，在遍历每个方向上的点时，如果点存在就推入一个中间队列，作为下一轮遍历的源点

大体就以上两步，一个搜索过程，一个确定起点并更新起点。

但是在本题中，他是多源BFS，会有中间相遇的情况，所以在判断此点是否可以赋值的时候加入了一个判断isWater[x][y] > count，此处的count是第几层遍历，也就是当前最大值。我们初始化陆地的高度为Infinity，只有当前点是Infinity才可以赋值，反之就跳过。

/** * @param {number[][]} isWater * @return {number[][]} */ var highestPeak = function (isWater) { const direction = [[0, -1], [0, 1], [-1, 0], [1, 0]] //上下左右 const m = isWater.length, n = isWater[0].length let water = [] isWater.forEach((v, i) => { v.forEach((v, j) => { v == 1 ? (water.push([i, j])) && (isWater[i][j] = 0) : (isWater[i][j] = Infinity) }) }) let count = 1 while (water.length > 0) { const _arr = [] water.forEach((point) => { direction.forEach((dir) => { let x = point[0] + dir[0] let y = point[1] + dir[1] if (x >= 0 && y >= 0 && x < m && y < n && isWater[x][y] > count) {//这里的判断 isWater[x][y] = count _arr.push([x, y]) } }) }) water = _arr count++ } return isWater };

12345678910111213141516171819202122232425262728293031