---
description: BFS
---

# 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:**

![](https://assets.leetcode.com/uploads/2021/01/10/screenshot-2021-01-11-at-82045-am.png)

```
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:**

![](https://assets.leetcode.com/uploads/2021/01/10/screenshot-2021-01-11-at-82050-am.png)

```
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.
```

**Constraints:**

* `m == isWater.length`
* `n == isWater[i].length`
* `1 <= m, n <= 1000`
* `isWater[i][j]` is `0` or `1`.
* There is at least **one** water cell.

## Solution:

[English Version in Youtube](https://youtu.be/rMH2WLcD-Tc)

[中文版解答Youtube Link](https://youtu.be/9bFC2CLXynM)

[中文版解答Bilibili Link](https://member.bilibili.com/platform/upload-manager/article)

```
class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int m = isWater.size();
        int n = isWater.front().size();
        vector<vector<int>> result(m, vector<int>(n, -1));
        
        queue<pair<int, int>> myqueue;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isWater[i][j] == 1) {
                    myqueue.push({i, j});
                    result[i][j] = 0;
                }
            }
        }
        
        int cur_height = 0;
        while (!myqueue.empty()) {
            int total = myqueue.size();
            
            for (int k = 0; k < total; k++) {
                pair<int, int> pos = myqueue.front();
                myqueue.pop();
                
                pair<int, int> directions[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
                for (pair<int, int> direction : directions) {
                    int new_pos_x = pos.first + direction.first;
                    int new_pos_y = pos.second + direction.second;
                    if (new_pos_x < 0 || new_pos_x >= m|| new_pos_y < 0 || new_pos_y >= n
                        || result[new_pos_x][new_pos_y] != -1) {
                        continue;
                    }
                    myqueue.push({new_pos_x, new_pos_y});
                    result[new_pos_x][new_pos_y] = cur_height + 1;
                }
            }
            
            cur_height++;
        }
        
        return result;
    }
};
```
