leetcode-1706 地图中的最高点

1765. 地图中的最高点 - 力扣（LeetCode） (leetcode-cn.com)

题目

给你一个大小为 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) 的高度。如果有多种解法，请返回 任意一个 。

题意

由二维矩阵表示地图，其中0表示陆地，1表示水域，规定水域的高度必须为0，陆地的高度任意，但是地图中任意相邻的格子高度差至多为1。求一种安排方案，使得矩阵中的最高高度值最大。

思路

首先想到的是广度优先搜索。但是一般的广度优先搜索只能从一个水域出发，无法保证其他水域周围的格子也满足题目要求，因此本地应该使用多源广度优先搜索。

对于每个水域周围的节点，从水域出发，对于每个陆地，他的最大值只受距离其最近的水域的影响，因此符合多源广度优先搜索的条件。

代码

/*
 * @File Name          :leetcode-1765.cpp
 * @Author             :cc
 * @Version            :1.0.0
 * @Date               :2022/1/29 10:35
 * @Description        :
 * @Function List      :
 * @History            :
 */

#include "vector"
#include "queue"
#include "algorithm"

using namespace std;

class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>> &isWater) {
        int m = isWater.size();
        int n = isWater[0].size();
        vector<vector<int>> ans(m, vector<int>(n, -1));
        queue<pair<int, int>> que;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (isWater[i][j] == 1) {
                    ans[i][j] = 0;
                    que.emplace(i, j);
                }
        int dx[] = {0, 0, 1, -1};
        int dy[] = {1, -1, 0, 0};

        while (!que.empty()){
            pair<int, int> p = que.front();
            que.pop();
            for(int i = 0; i < 4; i++){
                int sx = p.first+dx[i];
                int sy = p.second+dy[i];
                if(sx >= 0 && sy >= 0 && sx < m && sy < n && ans[sx][sy] == -1){
                    ans[sx][sy] = ans[p.first][p.second]+1;
                    que.emplace(sx,sy);
                }
            }
        }return ans;
    }
};