c++ - 编码正确逻辑时输出错误的原因？

Question

我在leetcode上解决this question:
我解决这个问题的策略是:

在每个dfs调用中为每个单元格索引(x，y)运行dfs

如果单元格是目标单元格，则相应地设置标志

如果两个标志都为真，则将此单元格添加到“ans” vector 中，否则继续下一个dfs

我的代码:

#include <iostream>
using namespace std;
#include <vector>



class Solution {
public:
    void psUtil(vector<vector<int> >&mat, int x, int y, int m, int n, int &isP, int &isA, vector<vector<int> >&vis, vector<vector<int> >&ans)
    {
        //check dstinations
        if(x == 0 || y == 0)
        {
            //cout << "P true" << " x and y are " << x << y << endl;
            isP = 1;
        }
        if(x == m-1 || y == n-1)
        {
            //cout << "A true" << " x and y are " << x << y << endl;
            isA = 1;
        }
        
        vector<int> cell(2);
        cell[0] = x;
        cell[1] = y;
        
        // check both dst rched
        if(isA && isP)
        {
            // append to ans
            //cout << "ans = " << cell[0] << " " << cell[1] << endl;
            ans.push_back(cell);
            return;
        }
        // mark vis
        vis.push_back(cell);
        
        int X[] = {-1, 0, 1, 0};
        int Y[] = {0, 1, 0, -1};
        int x1, y1;
        
        // check feasible neighbours
        for(int i = 0; i < 4; ++i)
        {
            x1 = x + X[i];
            y1 = y + Y[i];
            if(x1 < 0 || y1 < 0 || x1 >= m || y1 >= n) continue;

            //cout << "if(mat.at(x1).at(y1) <= mat.at(x).at(y))" << endl;
            
            if(mat.at(x1).at(y1) <= mat.at(x).at(y))
            { 
                vector<vector<int> > :: iterator it;
                vector<int> cell1(2);
                cell1[0] = x1;
                cell1[1] = y1;
                it = find(vis.begin(), vis.end(), cell1);
                if(it != vis.end())
                continue;
                psUtil(mat, x1, y1, m, n, isP, isA, vis, ans);
                if(isA && isP) return; 
            }
        }
    }
    vector<vector<int> > pacificAtlantic(vector<vector<int> >& matrix) 
    {
        // find dimensions
        int m = matrix.size(); // rows
        int n = matrix[0].size(); // cols
        vector<vector<int> >ans;
        // flags if rched destinations
        int isP, isA;
        isP = isA = 0;
        // iterate for all indices
        for(int x = 0; x < m; ++x)
        {
            for(int y = 0; y < n; ++y)
            {
                // visited nested vector
                vector<vector<int> >vis; 
                psUtil(matrix, x, y, m, n, isP, isA, vis, ans);
                isP = isA = 0;    
            }
        }
        return ans;     
    }
};
/*
int main()
{
    vector<vector<int> > mat{ {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} };
    Solution ob;
    vector<vector<int> > ans;
    ans = ob.pacificAtlantic(mat);
    for(int i = 0; i < ans.size(); ++i)
    {
        for(int j = 0; j < ans[0].size(); ++j)
        {
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}
*/

对于给定的样本输入，我的输出是:

0 4 
1 4 
0 3 
2 4 
4 0 
4 2 
4 0 

正确的输出应该是:

[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

该程序在哪里出错？

Answer 1

您的代码很难调试。这是一个具有深度优先搜索和备忘录功能的工作解决方案，易于理解:

#include <vector>

class Solution {
public:
    static inline constexpr int direction_row[4] = {0, 1, -1, 0};
    static inline constexpr int direction_col[4] = {1, 0, 0, -1};

    inline std::vector<std::vector<int>> pacificAtlantic(const std::vector<std::vector<int>> &grid) {
        std::vector<std::vector<int>> oceans = grid;
        std::vector<std::vector<int>> water_flows;
        const int row_length = oceans.size();

        if (!row_length) {
            return water_flows;
        }

        const int col_length = oceans[0].size();

        std::vector<std::vector<bool>> pacific(row_length, std::vector<bool>(col_length, false));
        std::vector<std::vector<bool>> atlantic(row_length, std::vector<bool>(col_length, false));

        for (int row = 0; row < row_length; row++) {
            depth_first_search(oceans, pacific, row, 0, INT_MIN);
            depth_first_search(oceans, atlantic, row, col_length - 1, INT_MIN);
        }

        for (int col = 0; col < col_length; col++) {
            depth_first_search(oceans, pacific, 0, col, INT_MIN);
            depth_first_search(oceans, atlantic, row_length - 1, col, INT_MIN);
        }

        for (int row = 0; row < row_length; row++)
            for (int col = 0; col < col_length; col++)
                if (pacific[row][col] && atlantic[row][col]) {
                    water_flows.push_back({row, col});
                }

        return water_flows;
    }

private:
    static inline void depth_first_search(const std::vector<std::vector<int>> &oceans, std::vector<std::vector<bool>> &visited, const int row, const int col, const int height) {
        if (row < 0 || row > oceans.size() - 1 || col < 0 || col > oceans[0].size() - 1 || visited[row][col]) {
            return;
        }

        if (oceans[row][col] < height) {
            return;
        }

        visited[row][col] = true;

        for (int iter = 0; iter < 4; iter++) {
            depth_first_search(oceans, visited, row + direction_row[iter], col + direction_col[iter], oceans[row][col]);
        }
    }

};

引用文献

有关更多详细信息，请参见Discussion Board。那里有很多接受的解决方案，其中包含各种languages和说明，高效的算法以及渐近time / space复杂度分析1，2。