LeetCode Pacific Atlantic Water Flow
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).
给定一个矩阵，每个元素表示一个方格中水柱的高度，左上角是太平洋，右下角是大西洋，问哪些坐标的水柱既能流向太平洋，又能流向大西洋。注意每个水柱能流向和它同样高或者比它第的地方。
一看就是DFS或者BFS的题。
拍脑袋解法。对于每个坐标，我们DFS看能否分别到达太平洋或者大西洋。代码如下：
[cpp]
vector<vector<int>> dirs = { { 0,-1 },{ -1,0 },{ 0,1 },{ 1,0 } }; // 0:left, 1:up, 2:right, 3:down
class Solution4 {
private:
int m, n;
bool isOk(int x, int y) {
return x >= 0 && x < m&&y >= 0 && y < n;
}
// type=0:Pacific; 1:Atlantic
bool dfs(vector<vector<int>>& matrix, vector<vector<int>>& visited, int x, int y, const int& type) {
for (int i = 0; i < dirs.size(); ++i) {
int xx = x + dirs[i][0], yy = y + dirs[i][1];
if (isOk(xx, yy) && visited[xx][yy] == 0 && matrix[x][y] >= matrix[xx][yy]) {
visited[xx][yy] = 1;
if (dfs(matrix, visited, xx, yy, type)) {
visited[xx][yy] = 0;
return true;
}
visited[xx][yy] = 0;
}
else if ((type == 0 && (xx < 0 || yy < 0)) || (type == 1 && (xx >= m || yy >= n))) {
return true;
}
}
return false;
}
public:
vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty())return{};
m = matrix.size(), n = matrix[0].size();
vector<vector<int>> visited(m, vector<int>(n, 0));
vector<pair<int, int>> ans;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
visited[i][j] = 1;
if (dfs(matrix,visited,i,j,0)&&dfs(matrix,visited,i,j,1))
ans.push_back(pair<int, int>(i, j));
visited[i][j] = 0;
}
}
return ans;
}
};
[/cpp]
本代码提交AC，用时702MS。
这种DFS的解法重复计算非常多，比如(a,b)这个点DFS时会经过(a-1,b-1)，而(a-1,b-1)之前其实已经DFS过了。可以在DFS的过程中记录下经过的点的DFS状态，比如在DFS(a,b)时，走到(a-1,b-1)，先查状态，发现(a-1,b-1)到不了大西洋，那现在这条路就没必要继续DFS下去了；相反，如果查状态发现(a-1,b-1)能到大西洋，则后续不需要再DFS其他路径了。
保存状态的DFS版本如下：
[cpp]
vector<vector<int>> dirs = { { 0,-1 },{ -1,0 },{ 0,1 },{ 1,0 } }; // 0:left, 1:up, 2:right, 3:down
// memory version
class Solution3 {
private:
int m, n;
bool isOk(int x, int y) {
return x >= 0 && x < m&&y >= 0 && y < n;
}
bool dfs(vector<vector<int>>& matrix, vector<vector<int>>& visited, int x, int y, const int& type, vector<vector<vector<int>>>& mem) {
for (int i = 0; i < dirs.size(); ++i) {
int xx = x + dirs[i][0], yy = y + dirs[i][1];
if (isOk(xx, yy) && visited[xx][yy] == 0 && matrix[x][y] >= matrix[xx][yy]) {
if (mem[xx][yy][type] == 1) {
mem[x][y][type] = 1;
return true;
}
else if (mem[xx][yy][type] == 0)continue;
visited[xx][yy] = 1;
if (dfs(matrix, visited, xx, yy, type, mem)) {
mem[x][y][type] = 1;
visited[xx][yy] = 0;
return true;
}
visited[xx][yy] = 0;
}
else if ((type == 0 && (xx < 0 || yy < 0)) || (type == 1 && (xx >= m || yy >= n))) {
mem[x][y][type] = 1;
return true;
}
}
mem[x][y][type] = 0;
return false;
}
public:
vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty())return{};
m = matrix.size(), n = matrix[0].size();
vector<vector<int>> visited(m, vector<int>(n, 0));
vector<vector<vector<int>>> mem(m, vector<vector<int>>(n, vector<int>(2, -1)));
vector<pair<int, int>> ans;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
visited[i][j] = 1;
if (mem[i][j][0] == -1)
dfs(matrix, visited, i, j, 0, mem);
if (mem[i][j][1] == -1)
dfs(matrix, visited, i, j, 1, mem);
visited[i][j] = 0;
if (mem[i][j][0] == 1 && mem[i][j][1] == 1)
ans.push_back(pair<int, int>(i, j));
}
}
return ans;
}
};
[/cpp]
无奈，在第112/113这个数据上WA了，但是这个数据太大了，面对的是汪洋大海，调试太费劲，暂时没fix bug。
看了下讨论区，发现主流解法是从海洋开始BFS，分别从大西洋和太平洋BFS，记录下两个海洋分别能访问到的点，最后如果某个点同时被两个海洋访问到了，则说明该点既能到达大西洋，也能到达太平洋。
代码如下：
[cpp]
vector<vector<int>> dirs = { { 0,-1 },{ -1,0 },{ 0,1 },{ 1,0 } }; // 0:left, 1:up, 2:right, 3:down
class Solution {
private:
int m, n;
bool isOk(int x, int y) {
return x >= 0 && x < m&&y >= 0 && y < n;
}
void bfs(vector<vector<int>>& matrix, queue<pair<int, int>>& Q, vector<vector<int>>& visited) {
while (!Q.empty()) {
auto f = Q.front();
Q.pop();
visited[f.first][f.second] = 1;
for (int i = 0; i < dirs.size(); ++i) {
int x = f.first + dirs[i][0], y = f.second + dirs[i][1];
if (isOk(x, y) && visited[x][y] == 0 && matrix[f.first][f.second] <= matrix[x][y]) {
Q.push(pair<int, int>(x, y));
}
}
}
}
public:
vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty())return{};
m = matrix.size(), n = matrix[0].size();
vector<vector<int>> pacific(m, vector<int>(n, 0)), atlantic(m, vector<int>(n, 0));
queue<pair<int, int>> pQ, aQ;
for (int i = 0; i < m; ++i) { // vertical
pQ.push(pair<int, int>(i, 0));
aQ.push(pair<int, int>(i, n – 1));
}
for (int i = 0; i < n; ++i) { // horizontal
pQ.push(pair<int, int>(0, i));
aQ.push(pair<int, int>(m – 1, i));
}
bfs(matrix, pQ, pacific);
bfs(matrix, aQ, atlantic);
vector<pair<int, int>> ans;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (pacific[i][j] == 1 && atlantic[i][j] == 1)
ans.push_back(pair<int, int>(i, j));
}
}
return ans;
}
};
[/cpp]
本代码提交AC，用时减少到45MS。
对于类似的搜索题目，如果是求单个点能否达到目的地，则从起始点或者目的点开始BFS/DFS的效果都是一样的。但是如果要求所有能到达目的点的点，则从目的点开始BFS就能一次性找到这些点，而从每个起始点开始BFS/DFS就非常费劲了。]]>