我试图解决 this challenge
这是我的解决方案
class Solution {
public:
vector<pair<int, int>> result;
map<pair<int, int>, pair<bool, bool>> dp;
// P A
pair<bool, bool> doPacific(vector<vector<int>>& matrix, vector<vector<bool>> & visited, int row, int col)
{
cout << row << ' ' << col << endl;
if(col < 0 || row < 0)
{
return pair<bool, bool>(true, false);
}
if(col >= matrix[0].size() || row >= matrix.size())
{
return pair<bool, bool>(false, true);
}
if(visited[row][col])
{
return dp[make_pair(row, col)];
}
pair<bool,bool> left(false, false);
pair<bool,bool> right(false, false);
pair<bool,bool> top(false, false);
pair<bool,bool> bottom(false, false);
visited[row][col] = true;
// Go Down if index is invalid or has valid index and water level
if(((row + 1 < matrix.size()) && (matrix[row + 1][col] <= matrix[row][col])) || row + 1 >= matrix.size())
{
bottom = doPacific(matrix,visited, row + 1, col);
}
if(((row - 1 >= 0) && (matrix[row - 1][col] <= matrix[row][col])) || (row -1 < 0))
{
top = doPacific(matrix,visited, row - 1, col);
}
if(((col + 1 < matrix[0].size()) && (matrix[row][col + 1] <= matrix[row][col])) || (col + 1>= matrix[0].size()))
{
right = doPacific(matrix,visited, row, col + 1);
}
if(((col - 1 >=0) && (matrix[row][col - 1] <= matrix[row][col])) || (col -1 < 0))
{
left = doPacific(matrix,visited, row, col - 1);
}
pair<bool, bool>returnValue(false, false);
returnValue.first |= left.first;
returnValue.second |= left.second;
returnValue.first |= right.first;
returnValue.second |= right.second;
returnValue.first |= bottom.first;
returnValue.second |= bottom.second;
returnValue.first |= top.first;
returnValue.second |= top.second;
dp.insert(make_pair(make_pair(row, col), returnValue));
if(returnValue.first && returnValue.second)
{
result.push_back(make_pair(row, col));
}
return returnValue;
}
vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
vector<vector<bool>> visited(matrix.size(), vector<bool>(matrix[0].size(), false));
result.clear();
dp.clear();
for(int i=0; i< matrix.size(); ++i)
{
for(int j=0; j < matrix[0].size(); ++j)
{
if(!visited[i][j])
{
doPacific(matrix, visited, i, j);
}
}
}
return result;
}
};
但是我的解决方案输入失败
[10,10,10]
[10, 1,10]
[10,10,10]
我的回答只省略了索引
(0,1) 。当我追踪递归树时，它看起来像这样。
(0, 0)
/
(1,0)
/
(2, 0)
/ \
(2, 1) (2, 2)
/ /
(T,F)/ (1,2)
(1, 1) /
(0,2)
/
(0,1) This return(T,F) when it should return (T,T).
Because (0,1) won't call (0,0) since it is
already being processed(i.e visited) which in turn depends on (0,1),
creating a cycle. Although there exists a path
from (0,0) to atlantic
我的问题是当现有节点和要添加的节点之间存在循环依赖时，我该如何解决这种情况。
解决此类问题的方法是否正确。
最佳答案
您的实现中有多个问题:
not visited 和 visited 。但你确实可以落入第三种状态。通常我们会考虑颜色 white 、 gray 和 black 。在您的代码中，gray 和 black 颜色在单个 visited 状态中合并在一起。 visited 你就不会再次访问它，而只是在你的 dp 数组中查找它的值。正如您自己发现的那样，它不起作用，因为 dp 数组仅适用于 black 单元格，而不适用于 gray 单元格。但由于问题 1. 你不能有所作为 您的
dp 数组没有为 gray 单元正确更新的原因是您尝试同时做两件事:但是使用单个 DFS，您可以更新前向路径上的一个属性，而第二个仅在您遍历的后向路径上。
一种解决方案是使用两个 DFS 分别更新每个属性。
您可以尝试从一个海洋开始然后从第二个海洋开始做两个 flood-fill，而不是单个 DFS。每个洪水填充都是一个 DFS，但来自不同的来源，并更新不同的
visited 属性。显然，您反转了流动的条件，即您的水从低处流向高处。在两次洪水填充之后，您最终会输出两洋接触的所有单元格。 Flood-fill 是
O(n*m)，因此与您当前的实现相比，它不会降低复杂性。在我的实现中，我为每个海洋开始了
n+m 洪水填充，但我保留了相同的 visiteds map ，所以它仍然保留在 O(n*m) 中这是一个示例解决方案(可读但仍然比 91% 的 c++ 提交快)。看到我使用位掩码技术来标记海洋访问的单元格(1 -> 太平洋，2 -> 大西洋，3 -> 两者)而不是
pair<bool,bool> 但这只是为了性能优化。int width, height;
vector<vector<unsigned char>> visiteds;
void floodFill(int i, int j, unsigned char mask, vector<vector<int>>& matrix) {
visiteds[i][j] = visiteds[i][j] | mask;
auto& h = matrix[i][j];
if(i > 0 && matrix[i-1][j] >= h && !(visiteds[i-1][j] & mask))
floodFill(i-1, j, mask, matrix);
if(i < height-1 && matrix[i+1][j] >= h && !(visiteds[i+1][j] & mask))
floodFill(i+1, j, mask, matrix);
if(j > 0 && matrix[i][j-1] >= h && !(visiteds[i][j-1] & mask))
floodFill(i, j-1, mask, matrix);
if(j < width-1 && matrix[i][j+1] >= h && !(visiteds[i][j+1] & mask))
floodFill(i, j+1, mask, matrix);
}
vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
vector<pair<int,int>> cells;
height = matrix.size();
if(! height)
return cells;
width = matrix[0].size();
visiteds.clear();
visiteds.resize(height, vector<unsigned char>(width, 0));
for(int k=0; k<height; ++k) {
floodFill(k, 0, 1, matrix);
floodFill(k, width-1, 2, matrix);
}
for(int k=0; k<width; ++k) {
floodFill(0, k, 1, matrix);
floodFill(height-1, k, 2, matrix);
}
for(size_t i=0; i<height; ++i)
for(size_t j=0; j<width; ++j)
if(visiteds[i][j] == 3)
cells.push_back(make_pair(i, j));
return cells;
}
关于algorithm - 具有循环依赖的 DFS，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/46659605/