题目

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

解答

根据题意，肯定是先从水域开始进行遍历，将所有水域的上下左右（如果存在）的高度都置1，然后对所有高度为1的地域进行遍历，将其上下左右的高度置2，依次循环……

这就是BFS问题，但是由于水域数量的不唯一性，所以需要进行多点的BFS，因此可以引入数据结构【队列】来完成遍历，即如果遍历到对应的地域且进行了高度设置，就将该地点放入到队列中即可。

参考代码完成思路：

class Solution {
private:
    // 用来上下左右遍历
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {1, -1, 0, 0};
public:
    vector<vector<int>> highestPeak(vector<vector<int>> &isWater) {
        int m = isWater.size();
        int n = isWater[0].size();
      
        queue<pair<int, int>> q; // 队列，用来记录要BFS的点
        vector<vector<int>> ret(m, vector<int>(n, -1)); // 初始化为 -1
		
      	// 遍历以将所有水域高度置0
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (isWater[i][j] == 1) {
                    // = 1表明是水域，放入队列
                    ret[i][j] = 0;  // 设置高度
                    q.push({i, j}); // 将该点加入队列
                }
            }
        }
		
      	// 队列不空，则表明仍需遍历
        while (!q.empty()) {
          	// 出队
            auto get = q.front();
            q.pop();
          
          	// 对出队的点进行上下左右检查
            for (int i = 0; i < 4; ++i) {
                int x = get.first + dx[i];
                int y = get.second + dy[i];

                // 超出边界 & 已经遍历过
                if (x < 0 || x >= m || y < 0 || y >= n ||
                    ret[x][y] >= 0) {
                    continue;
                }

                ret[x][y] = ret[get.first][get.second] + 1;
                q.push({x, y});
            }
        }

        return ret;
    }
};