老师能否帮我看下LeetCode417大西洋水流问题
来源:8-8 回溯法是经典人工智能的基础 N Queens
栗子小悠
2020-03-14
老师您好,这道题是我看了老师的第8-7讲做的。思路是按照DFS的思路,仿照了200题岛屿问题的代码。从可以到达大西洋或者太平洋边上的点进行DFS搜索,满足条件的都保存为true。最后取交集得到结果。现在DFS函数中显示会出现两个点来回跳跃的情况。我参考的一个LeetCode题解也是这个思路,我看感觉代码的写法虽然不一样,思路上是一样的。他的就可以跑通,感觉很疑惑。没有感觉到有什么区别,希望老师帮看下我的问题在哪里。如果老师也有自己的LeetCode github代码,求一下链接。
我自己的会堆栈溢出的代码如下:`class Solution {
int d[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
bool IfValid(const vector<vector<int>>& matrix, int x, int y)
{
if( x<0 || x>=matrix.size() || y<0 || y>=matrix[0].size())
{
return false;
}
return true;
}
void DFS(const vector<vector<int>>& matrix,const int x,const int y,vector<vector<bool>>& res)
{
res[x][y] = true;
for(int i=0;i<4;i++)
{
int newx = x+d[i][0];
int newy = y+ d[i][1];
if(IfValid(matrix,newx,newy) && matrix[newx][newy] >= matrix[x][y])
{
cout<<"newx="<<newx<<"newy="<<newy<<endl;
DFS(matrix,newx,newy,res);
}
}
return;
}
public:
vector<vector> pacificAtlantic(vector<vector>& matrix) {
vector<vector> positionResult;
int height = matrix.size();
if(height == 0) return positionResult;
int length = matrix[0].size();
vector<vector> toTai(height,vector(length,false));
vector<vector> toDa(height,vector(length,false));
//利用DFS的方式从边上开始遍历完成
for( int i=0;i<height;i++)
{
DFS(matrix,i,0, toTai);
DFS(matrix,i,length-1,toDa);
}
for(int i=0; i<length;i++)
{
DFS(matrix,0,i,toTai);
DFS(matrix,height-1,i,toDa);
}
//去交集
for(int i=0; i<height; i++)
{
for(int j=0; j<length; j++)
{
if(toDa[i][j] && toTai[i][j])
{
vector<int> one;
one.push_back(i);
one.push_back(j);
positionResult.push_back(one);
}
}
}
return positionResult;
}
};`
我参考的可以跑通的代码如下:
class Solution {
public:
vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return {};
vector<pair<int, int>> res;
int m = matrix.size(), n = matrix[0].size();
vector<vector<bool>> pacific(m, vector<bool>(n, false));
vector<vector<bool>> atlantic(m, vector<bool>(n, false));
for (int i = 0; i < m; ++i) {
dfs(matrix, pacific, INT_MIN, i, 0);
dfs(matrix, atlantic, INT_MIN, i, n - 1);
}
for (int i = 0; i < n; ++i) {
dfs(matrix, pacific, INT_MIN, 0, i);
dfs(matrix, atlantic, INT_MIN, m - 1, i);
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (pacific[i][j] && atlantic[i][j]) {
res.push_back({i, j});
}
}
}
return res;
}
void dfs(vector<vector<int>>& matrix, vector<vector<bool>>& visited, int pre, int i, int j) {
int m = matrix.size(), n = matrix[0].size();
if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || matrix[i][j] < pre) return;
visited[i][j] = true;
dfs(matrix, visited, matrix[i][j], i + 1, j);
dfs(matrix, visited, matrix[i][j], i - 1, j);
dfs(matrix, visited, matrix[i][j], i, j + 1);
dfs(matrix, visited, matrix[i][j], i, j - 1);
}
};
1回答
-
liuyubobobo
2020-03-14
要解决你现在的无限递归的问题,你需要在 DFS 的递归调用前的那个判断,加上对 res 的判断,即:
if( IfValid(matrix,newx,newy) && matrix[newx][newy] >= matrix[x][y] && !res[newx][newy]){ // 这里!!! // cout<<"newx="<<newx<<"newy="<<newy<<endl; DFS(matrix,newx,newy,res); }
不然的话,你的 res 只是在 dfs 中做了一下赋值,没有被使用。
继续加油!:)
10
相似问题