leetcode第 417. Pacific Atlantic Water Flow题对测试用例结果有疑问
来源:8-7 floodfill算法,一类经典问题 Number of Islands-
weixin_慕慕4340848
2021-02-01
老师您好!leetcode第 417. Pacific Atlantic Water Flow题。我觉得测试用例给的有点问题。代码如下:
int d[4][2]{ {0,-1},{-1,0},{0,1},{1,0} };
const int InVisited = -1, None = 0, Pacific = 1, Atlantic = 2, All = 3;
vector<vector>typeOfCeils;
bool isValidateCile(vector<vector>& matrix,int x, int y)
{
return x >= 0 && y >= 0 && x <(int) matrix[0].size() &&y< (int)matrix.size();
}
int pacificAtlantic(vector<vector>& matrix,int x,int y)
{
typeOfCeils[y][x] = None;
for (int i = 0; i < 4; ++i)
{
int newX = x + d[i][0];
int newY = y + d[i][1];
if (isValidateCile(matrix, newX, newY) && matrix[y][x] < matrix[newY][newX])
continue;
if (isValidateCile(matrix, newX, newY) && typeOfCeils[newY][newX] != InVisited) {
typeOfCeils[y][x] |= typeOfCeils[newY][newX];
continue;
}
if (newX < 0 || newY < 0) {
typeOfCeils[y][x] |= Pacific;
}
if (newX >= (int)matrix[0].size() || newY >= (int)matrix.size())
{
typeOfCeils[y][x] |=Atlantic;
}
if (!isValidateCile(matrix, newX, newY))
continue;
typeOfCeils[newY][newX] |= typeOfCeils[y][x];
typeOfCeils[y][x] |=pacificAtlantic(matrix,newX,newY);
}
return typeOfCeils[y][x];
}
vector<vector> pacificAtlantic(vector<vector>& matrix) {
vector<vector> res;
if (matrix.empty())
return res;
typeOfCeils = vector<vector>(matrix.size(), vector(matrix[0].size(), InVisited));
for (int i = 0; i < matrix.size(); ++i)
{
for (int j = 0; j < matrix[0].size(); ++j)
{
int type= pacificAtlantic(matrix, j, i);
if (type == All)
res.push_back({ i,j });
}
}
return res;
}
测试用例如下。其中(11,3)这个点我觉得应该是只有一条到大西洋得路径,没有到太平洋得路径。但是题目得解中包含了这个点。您能帮我看以下吗?谢谢
{7,1,17,13,9,10,5,14,0,3},
{7,15,7,8,15,16,10,10,5,13},
{18,9,15,8,19,16,7,5,5,10},
{15,11,18,3,1,17,6,4,10,19},
{3,16,19,12,12,19,2,14,5,9},
{7,16,0,13,14,7,2,8,6,19},
{5,10,1,10,2,12,19,1,0,19},
{13,18,19,12,17,17,4,5,8,2},
{2,1,17,13,14,12,14,2,16,10},
{5,8,1,11,16,1,18,15,6,19},
{3,8,14,14,5,0,2,7,5,1},
{17,1,9,17,10,10,10,7,1,16},
{14,18,5,11,17,15,8,8,14,13},
{6,4,10,17,8,0,11,4,2,8},
{16,11,17,9,3,2,11,0,6,5},
{12,18,18,11,1,7,12,16,12,12},
{2,14,12,0,2,8,5,10,7,0},
{16,13,1,19,8,13,11,8,11,3},
{11,2,8,19,6,14,14,6,16,12},
{18,0,18,10,16,15,15,12,4,3},
{8,15,9,13,8,2,6,11,17,6},
{7,3,0,18,7,12,2,3,12,10},
{7,9,13,0,11,16,9,9,12,13},
{9,4,19,6,8,10,12,6,7,11},
{5,9,18,0,4,9,6,4,0,1},
{9,12,1,11,13,13,0,16,0,6},
{7,15,4,8,15,17,17,19,15,1},
{7,17,4,1,1,14,10,19,10,19},
{10,5,12,5,8,8,14,14,6,0},
{16,10,10,7,13,4,0,15,18,0},
{11,2,10,6,5,13,4,5,3,1},
{9,14,16,14,15,3,2,13,17,8},
{19,2,10,1,2,15,12,10,2,5},
{12,4,8,9,8,6,4,14,14,0},
{11,17,17,4,16,13,6,15,5,7},
{12,18,1,3,9,10,7,1,1,1},
{18,6,10,8,12,14,9,12,10,3},
{15,13,18,13,8,5,12,14,18,0},
{15,4,8,9,19,18,6,19,12,0},
{4,14,15,4,17,17,9,17,9,0},
{6,17,16,10,3,8,8,18,15,9},
{3,8,4,2,13,0,2,8,8,2},
{14,12,13,12,17,4,16,9,8,7},
{0,19,8,16,1,13,7,6,15,11},
{1,13,16,14,10,4,11,19,9,13},
{8,0,2,1,16,12,16,9,9,9},
{5,2,10,4,8,12,17,0,2,15},
{11,2,15,15,14,9,11,19,18,11},
{4,4,1,5,13,19,9,17,17,17},
{4,1,8,0,8,19,11,0,5,4},
{8,16,14,18,12,2,0,19,0,13},
{7,11,3,18,8,2,2,19,8,7},
{3,13,6,1,12,16,4,13,0,5},
{12,1,16,19,2,12,16,15,19,6},
{1,7,12,15,3,3,13,17,16,12}
1回答
-
我把这个测试用例打印出来了。只看前 11 行就能找到相应的路径了。(11, 3)的位置应该是图示的 17:
继续加油!:)
022021-02-02
相似问题