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};