Given an m x n
matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.
Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.
Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.
Note:
- The order of returned grid coordinates does not matter.
- Both m and n are less than 150.
Example:
Given the following 5x5 matrix: Pacific ~ ~ ~ ~ ~ ~ 1 2 2 3 (5) * ~ 3 2 3 (4) (4) * ~ 2 4 (5) 3 1 * ~ (6) (7) 1 4 5 * ~ (5) 1 1 2 4 * * * * * * Atlantic Return: [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).
Solution: DFS/BFS
Be careful with the input range, easy to TLE with a naive implementation. Have to search from the boards.
Time complexity: O(mn)
Space complexity: O(mn)
DFS
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 |
// Author: Huahua, running time: 48 ms class Solution { public: vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) { if (matrix.empty()) return {}; const int n = matrix.size(); const int m = matrix[0].size(); vector<vector<int>> p(n, vector<int>(m)); vector<vector<int>> a(n, vector<int>(m)); for (int x = 0; x < m; ++x) { dfs(matrix, x, 0, 0, p); // top dfs(matrix, x, n - 1, 0, a); // bottom } for (int y = 0; y < n; ++y) { dfs(matrix, 0, y, 0, p); // left dfs(matrix, m - 1, y, 0, a); // right } vector<pair<int, int>> ans; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (p[i][j] && a[i][j]) ans.emplace_back(i, j); return ans; } private: void dfs(vector<vector<int>>& b, int x, int y, int h, vector<vector<int>>& v) { if (x < 0 || y < 0 || x == b[0].size() || y == b.size()) return; if (v[y][x] || b[y][x] < h) return; v[y][x] = true; dfs(b, x + 1, y, b[y][x], v); dfs(b, x - 1, y, b[y][x], v); dfs(b, x, y + 1, b[y][x], v); dfs(b, x, y - 1, b[y][x], v); } }; |
BFS
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 |
class Solution { public: vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) { if (matrix.empty()) return {}; const int n = matrix.size(); const int m = matrix[0].size(); const vector<int> dirs{0, 1, 0, -1, 0}; auto bfs = [&](queue<pair<int, int>>& q, vector<vector<int>>& v) { while (!q.empty()) { const int y = q.front().first; const int x = q.front().second; q.pop(); const int h = matrix[y][x]; v[y][x] = true; for (int i = 0; i < 4; ++i) { int tx = x + dirs[i]; int ty = y + dirs[i + 1]; if (tx < 0 || ty < 0 || tx == m || ty == n || matrix[ty][tx] < h) continue; if (v[ty][tx]) continue; q.push({ty, tx}); } } }; queue<pair<int, int>> qp; queue<pair<int, int>> qa; vector<vector<int>> vp(n, vector<int>(m)); vector<vector<int>> va(n, vector<int>(m)); for (int x = 0; x < m; ++x) { qp.push({0, x}); // top qa.push({n - 1, x}); // bottom } for (int y = 0; y < n; ++y) { qp.push({y, 0}); // left qa.push({y, m - 1}); // right } bfs(qp, vp); bfs(qa, va); vector<pair<int, int>> ans; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (vp[i][j] && va[i][j]) ans.emplace_back(i, j); return ans; } }; |
DP
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 |
// Author: Huahua, running time: 104 ms class Solution { public: vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) { if (matrix.empty()) return {}; const int n = matrix.size(); const int m = matrix[0].size(); vector<vector<int>> dp(n, vector<int>(m)); for (int x = 0; x < m; ++x) { dp[0][x] |= 1; dp[n - 1][x] |= 2; } for (int y = 0; y < n; ++y) { dp[y][0] |= 1; dp[y][m - 1] |= 2; } const vector<int> dirs{0, -1, 0, 1, 0}; while (true) { bool changed = false; for (int y = 0; y < n; ++y) for (int x = 0; x < m; ++x) for (int d = 0; d < 4; ++d) { const int tx = x + dirs[d]; const int ty = y + dirs[d + 1]; if (tx < 0 || ty < 0 || tx == m || ty == n || matrix[y][x] < matrix[ty][tx] || (dp[y][x] | dp[ty][tx]) == dp[y][x]) continue; dp[y][x] |= dp[ty][tx]; changed = true; } if (!changed) break; } vector<pair<int, int>> ans; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (dp[i][j] == 3) ans.emplace_back(i, j); return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment