1765.地图中的最高点

链接：1765.地图中的最高点
难度：Medium
标签：广度优先搜索、数组、矩阵
简介：请你返回一个大小为 m x n 的整数矩阵 height ，其中 height[i][j] 是格子 (i, j) 的高度。如果有多种解法，请返回 任意一个 。

题解 1 - cpp

• 编辑时间：2022-01-29
• 执行用时：284ms
• 内存消耗：105.6MB
• 编程语言：cpp
• 解法介绍：bfs。

class Solution {
   public:
    struct node {
        int row, col;
    };
    int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    vector<vector<int>> highestPeak(vector<vector<int>> &isWater) {
        int m = isWater.size(), n = isWater[0].size();
        vector<vector<int>> ans(m, vector(n, -1));
        queue<node> q;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isWater[i][j] == 1) {
                    q.push((node){i, j});
                    ans[i][j] = 0;
                }
            }
        }
        while (q.size()) {
            node v = q.front();
            q.pop();
            for (int i = 0; i < 4; i++) {
                int nrow = v.row + dirs[i][0], ncol = v.col + dirs[i][1];
                if (nrow < 0 || ncol < 0 || nrow >= m || ncol >= n ||
                    ans[nrow][ncol] != -1)
                    continue;
                ans[nrow][ncol] = ans[v.row][v.col] + 1;
                q.push((node){nrow, ncol});
            }
        }
        return ans;
    }
};