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回答

liuyubobobo

2021-02-02

我把这个测试用例打印出来了。只看前 11 行就能找到相应的路径了。(11, 3)的位置应该是图示的 17:


//img.mukewang.com/szimg/601830dc09d2dd1b04830584.jpg


继续加油!:)

0
2
weixin_慕慕4340848
谢谢老师!是我看错了;修改程序后再提交已经通过了
2021-02-02
共2条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7408 学习 · 1150 问题

查看课程