LeetCode 1765. Map of Highest Peak

You are given an integer matrix isWater of size m x n that represents a map of land and water cells.

• If isWater[i][j] == 0, cell (i, j) is a land cell.

• If isWater[i][j] == 1, cell (i, j) is a water cell.

You must assign each cell a height in a way that follows these rules:

• The height of each cell must be non-negative.

• If the cell is a water cell, its height must be 0.

• Any two adjacent cells must have an absolute height difference of at most 1. A cell is adjacent to another cell if the former is directly north, east, south, or west of the latter (i.e., their sides are touching).

Find an assignment of heights such that the maximum height in the matrix is maximized.

Return an integer matrix height of size m x n where height[i][j] is cell (i, j)'s height. If there are multiple solutions, return any of them.

Example 1:

Input: isWater = [[0,1],[0,0]]

Output: [[1,0],[2,1]]

Explanation: 

                    The image shows the assigned heights of each cell. The blue cell is the water cell, and the green cells are the land cells.

Example 2:

Input: isWater = [[0,0,1],[1,0,0],[0,0,0]]

Output: [[1,1,0],[0,1,1],[1,2,2]]

Explanation: 

                    A height of 2 is the maximum possible height of any assignment. Any height assignment that has a maximum height of 2 while still meeting the rules will also be accepted.

-----------------------------------------------------------

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

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/map-of-highest-peak

经典的BFS，只是对于多源的处理，先将所有的水的地址放到Deque中，然后依次遍历，

遍历后，将新的元素放到Deque中继续遍历，（只遍历标记是陆地，且位置高度是-1的，也就是之前没有遍历到的）

下面是代码：

Runtime: 66 ms, faster than 59.02% of Java online submissions for Map of Highest Peak.

Memory Usage: 166.9 MB, less than 16.39% of Java online submissions for Map of Highest Peak.