leetcode/1765.cpp at master · ganpengpeng/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include "common.h"

using namespace std;

constexpr int PEAK_MAX = 9999;

class Solution {
 public:
  vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
    int n = isWater.size();
    int m = isWater[0].size();
    vector<vector<int>> land_map(n, vector<int>(m, PEAK_MAX));
    queue<pair<int, int>> q;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (isWater[i][j]) {
          land_map[i][j] = 0;
          q.emplace(i, j);
        }
      }
    }
    while (!q.empty()) {
      auto coord = q.front();
      q.pop();
      if (coord.first > 0 && land_map[coord.first - 1][coord.second] == PEAK_MAX) {
        land_map[coord.first - 1][coord.second] =
            std::min(land_map[coord.first][coord.second] + 1, land_map[coord.first - 1][coord.second]);
        q.emplace(coord.first - 1, coord.second);
      }
      if (coord.first < n - 1 && land_map[coord.first + 1][coord.second] == PEAK_MAX) {
        land_map[coord.first + 1][coord.second] =
            std::min(land_map[coord.first][coord.second] + 1, land_map[coord.first + 1][coord.second]);
        q.emplace(coord.first + 1, coord.second);
      }
      if (coord.second > 0 && land_map[coord.first][coord.second - 1] == PEAK_MAX) {
        land_map[coord.first][coord.second - 1] =
            std::min(land_map[coord.first][coord.second] + 1, land_map[coord.first][coord.second - 1]);
        q.emplace(coord.first, coord.second - 1);
      }
      if (coord.second < m - 1 && land_map[coord.first][coord.second + 1] == PEAK_MAX) {
        land_map[coord.first][coord.second + 1] =
            std::min(land_map[coord.first][coord.second] + 1, land_map[coord.first][coord.second + 1]);
        q.emplace(coord.first, coord.second + 1);
      }
    }
    return land_map;
  }
};

int main() {
  Solution s;
  // vector<vector<int>> v = {{0, 1}, {0, 0}};
  // vector<vector<int>> v = {{0, 0, 1}, {1, 0, 0}, {0, 0, 0}};
  vector<vector<int>> v = {{0, 0, 0, 0, 0, 0, 1, 0},
                           {0, 1, 0, 0, 0, 0, 0, 0},
                           {0, 0, 0, 0, 0, 0, 0, 0},
                           {0, 0, 0, 0, 0, 0, 0, 0},
                           {0, 0, 0, 0, 0, 0, 0, 0},
                           {0, 0, 0, 0, 0, 0, 0, 0},
                           {0, 0, 0, 0, 0, 0, 1, 0},
                           {0, 0, 1, 0, 0, 0, 0, 0}};
  Print2DVector(s.highestPeak(v));
  return 0;
}