leetcode

0 class Solution {

1 typedef vector<vector<int>> Matrix;

2 typedef vector<vector<bool>> Marked;

3 typedef queue<pair<int, int>> Queue;

4 const vector<pair<int, int>> offsets = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

5

6 int n, m;

7 int valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; }

8

9 void dfs(Matrix &mat, Marked &mark, int x, int y) {

10 if (mark[x][y]) return;

11 Queue q;

12

13 q.push({x, y}), mark[x][y] = true;

14 while (!q.empty()) {

15 auto [a, b] = q.front();

16 q.pop();

17 for (auto [oa, ob] : offsets) {

18 int x = a + oa, y = b + ob;

19 if (!valid(x, y) || mark[x][y] || mat[x][y] < mat[a][b]) continue;

20 mark[x][y] = true;

21 q.push({x, y});

22 }

23 }

24 }

25

26 public:

27 vector<vector<int>> pacificAtlantic(Matrix &heights) {

28 n = heights.size(), m = heights[0].size();

29 Marked pac(n, vector<bool>(m, false)), atl(n, vector<bool>(m, false));

30

31 for (int i = 0; i < n; i++) {

32 dfs(heights, pac, i, 0);

33 dfs(heights, atl, i, m - 1);

34 }

35

36 for (int i = 0; i < m; i++) {

37 dfs(heights, pac, 0, i);

38 dfs(heights, atl, n - 1, i);

39 }

40

41 vector<vector<int>> res;

42 for (int i = 0; i < n; i++)

43 for (int j = 0; j < m; j++)

44 if (pac[i][j] && atl[i][j]) res.push_back({i, j});

45

46 return res;

47 }

48 };