LeetCode

Editorial: LeetCode 1765 Map of Highest Peak

Editorial: LeetCode 1765 Map of Highest Peak

https://leetcode.com/problems/map-of-highest-peak/ from Google

Thinking process:

Typical BFS problem. The process is to find the water first, and then use BFS to expend the height.

Here is the code.

 1class Solution {
 2public:
 3    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
 4        queue<pair<int, int>> q;
 5        int R = isWater.size();
 6        int C = isWater[0].size();
 7        vector<vector<int>> ret(R, vector<int>(C, -1));
 8        for (int r=0; r<R; r++) {
 9            for (int c=0; c<C; c++) {
10                if (isWater[r][c]) {
11                    q.push({r, c});
12                    ret[r][c] = 0;
13                }
14            }
15        }
16        vector<int> dir{1, 0, -1, 0, 1};
17        int h = 1;
18        while (q.size()) {
19            int sz = q.size();
20            while (sz--) {
21                auto [r, c] = q.front(); q.pop();
22                for (int i=0; i<4; i++) {
23                    int nr = r + dir[i];
24                    int nc = c + dir[i+1];
25                    if (nr>=0 and nc>=0 and nr<R and nc<C and ret[nr][nc]==-1) {
26                        ret[nr][nc] = h;
27                        q.push({nr, nc});
28                    }
29                }
30            }
31            h++;
32        }
33        return ret;
34    }
35};
comments powered by Disqus