0417.cpp (1474B)
1 class Solution { 2 typedef vector<vector<int>> Matrix; 3 typedef vector<vector<bool>> Marked; 4 typedef queue<pair<int, int>> Queue; 5 const vector<pair<int, int>> offsets = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; 6 7 int n, m; 8 int valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; } 9 10 void dfs(Matrix &mat, Marked &mark, int x, int y) { 11 if (mark[x][y]) return; 12 Queue q; 13 14 q.push({x, y}), mark[x][y] = true; 15 while (!q.empty()) { 16 auto [a, b] = q.front(); 17 q.pop(); 18 for (auto [oa, ob] : offsets) { 19 int x = a + oa, y = b + ob; 20 if (!valid(x, y) || mark[x][y] || mat[x][y] < mat[a][b]) continue; 21 mark[x][y] = true; 22 q.push({x, y}); 23 } 24 } 25 } 26 27 public: 28 vector<vector<int>> pacificAtlantic(Matrix &heights) { 29 n = heights.size(), m = heights[0].size(); 30 Marked pac(n, vector<bool>(m, false)), atl(n, vector<bool>(m, false)); 31 32 for (int i = 0; i < n; i++) { 33 dfs(heights, pac, i, 0); 34 dfs(heights, atl, i, m - 1); 35 } 36 37 for (int i = 0; i < m; i++) { 38 dfs(heights, pac, 0, i); 39 dfs(heights, atl, n - 1, i); 40 } 41 42 vector<vector<int>> res; 43 for (int i = 0; i < n; i++) 44 for (int j = 0; j < m; j++) 45 if (pac[i][j] && atl[i][j]) res.push_back({i, j}); 46 47 return res; 48 } 49 };