1765. 地图中的最高点 : 多源 BFS 运用题-阿里云开发者社区

1765. 地图中的最高点 : 多源 BFS 运用题

2022-05-06 113

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 1765. 地图中的最高点 : 多源 BFS 运用题

网络异常，图片无法展示

题目描述

这是 LeetCode 上的 1765. 地图中的最高点 ，难度为中等。

Tag : 「图论搜索」、「多源 BFS」

给你一个大小为 m x n 的整数矩阵 isWater ，它代表了一个由陆地和水域单元格组成的地图。

如果 isWater[i][j] == 0 ，格子 (i, j) 是一个陆地格子。
如果 isWater[i][j] == 1 ，格子 (i, j) 是一个水域格子。

你需要按照如下规则给每个单元格安排高度：

每个格子的高度都必须是非负的。
如果一个格子是是水域，那么它的高度必须为 00 。
任意相邻的格子高度差至多为 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.lengthm==isWater.length
n == isWater[i].lengthn==isWater[i].length
1 <= m, n <= 10001<=m,n<=1000
isWater[i][j] 要么是 00 ，要么是 11 。
至少有 11 个水域格子。

多源 BFS

这是一道「多源 BFS」板子题，对「多源 BFS」不熟悉的同学，可以看看前置 🧀：多源 BFS 入门。

里面详解了「多源 BFS」与「单源 BFS」板子上的区别，强调了可以通过建立「虚拟源点」的方式，将「多源 BFS」转换回「单源 BFS」问题。

回到本题，题目规定了水域区域的高度为 00，然后相邻格子之间的高度差至多为 11，

我们可以将所有水域（高度为 00）区域进行入队，然后跑一遍 BFS 即可。

将所有水域（高度为 00）区域进行入队的操作可看作是将与「虚拟源点」链接的节点进行入队（也等价于起始只将虚拟源点入队）：

网络异常，图片无法展示

容易证明这样做法的正确性：对于一个「陆地」区域（高度可变）而言，其所能填入的高度，取决于其距离其他「水域」区域的距离，而我们最终要让整个答案矩阵合法，因此每个「陆地」区域应该取其所能填入的高度的「下界」，即只由「距离它最近的水域」区域所更新，这符合 BFS 的性质。

代码（感谢 @Benhao 和 @5cm/s 🌸 同学提供的其他语言版本）：

class Solution {
    public int[][] highestPeak(int[][] g) {
        int m = g.length, n = g[0].length;
        int[][] ans = new int[m][n];
        Deque<int[]> d = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == 1) d.addLast(new int[]{i, j});
                ans[i][j] = g[i][j] == 1 ? 0 : -1;
            }
        }
        int[][] dirs = new int[][]{{1,0}, {-1,0}, {0,1}, {0,-1}};
        int h = 1;
        while (!d.isEmpty()) {
            int size = d.size();
            while (size-- > 0) {
                int[] info = d.pollFirst();
                int x = info[0], y = info[1];
                for (int[] di : dirs) {
                    int nx = x + di[0], ny = y + di[1];
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                    if (ans[nx][ny] != -1) continue;
                    ans[nx][ny] = h;
                    d.addLast(new int[]{nx, ny});
                }
            }
            h++;
        }
        return ans;
    }
}
复制代码

class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        m, n = len(isWater), len(isWater[0])
        ans = [[0] * n for _ in range(m)]
        d = deque()
        for i in range(m):
            for j in range(n):
                if isWater[i][j]:
                    d.append((i, j))
                ans[i][j] = 0 if isWater[i][j] else -1
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        h = 1
        while d:
            size = len(d)
            for _ in range(size):
                x, y = d.popleft()
                for di in dirs:
                    nx, ny = x + di[0], y + di[1]
                    if 0 <= nx < m and 0 <= ny < n and ans[nx][ny] == -1:
                        ans[nx][ny] = h
                        d.append((nx, ny))
            h += 1
        return ans
复制代码

func highestPeak(isWater [][]int) [][]int {
    m, n := len(isWater), len(isWater[0])
    ans, d := make([][]int, m), [][]int{}
    for i := 0; i < m; i++ {
        ans[i] = make([]int, n)
        for j := 0; j < n; j++ {
            if isWater[i][j] == 1 {
                d = append(d, []int{i, j})
                ans[i][j] = 0
            } else {
                ans[i][j] = -1
            }
        }
    }
    dirs := [][]int{{1,0}, {-1,0}, {0,1}, {0,-1}}
    for h := 1; len(d) > 0; h++ {
        for size := len(d); size > 0; size--{
            info := d[0]
            d = d[1:]
            x, y := info[0], info[1]
            for _, di := range dirs {
                nx, ny := x + di[0], y + di[1]
                if nx >= 0 && nx < m && ny >= 0 && ny < n && ans[nx][ny] == -1 {
                    ans[nx][ny] = h
                    d = append(d, []int{nx, ny})
                }
            }
        }
    }
    return ans
}
复制代码

const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& g) {
        int n = g.size(), m = g[0].size();
        queue<pair<int, int>> q;
        vector<vector<int>> ans(n, vector<int>(m, 0));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (g[i][j] == 1) {
                    q.emplace(i, j);
                } else {
                    ans[i][j] = -1;
                }
            }
        }
        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            for (int i = 0; i < 4; ++i) {
                int a = x + dx[i], b = y + dy[i];
                if (a < 0 || a == n || b < 0 || b == m) continue;
                if (ans[a][b] >= 0) continue;
                ans[a][b] = ans[x][y] + 1;
                q.emplace(a, b);
            }
        }
        return ans;
    }
};
复制代码