运行时错误：将引用绑定到未对齐地址0xbebebebebebebec6上的类型为'int'的变量，该变量要求4字节对齐（stl_vector.h）。

Question

我正在编写代码解决Leetcode上这个问题

• 对于每个单元格索引(x,y)，运行深度优先搜索(dfs)
• 在每次dfs调用时，检查该单元格是否为目标单元格
• 相应地设置标志(flags)
• 如果两个标志都为true, 则将此单元格添加到"ans"向量(vector)中，否则继续下一个dfs

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)
        {
            isP = 1;
        }
        if(x == m || y == n)
        {
            isA = 1;
        }

        vector<int> cell(2);
        cell[0] = x;
        cell[1] = y;

        // check both dst rched
        if(isA && isP)
        {
            // append to ans
            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) continue;

            if(mat[x1][y1] <= mat[x][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());
                else 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;     
    }
};

运行时我的错误是：

Runtime Error Message:
Line 924: Char 9: runtime error: reference binding to misaligned address 0xbebebebebebebec6 for type 'int', which requires 4 byte alignment (stl_vector.h)
Last executed input:
[[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]]

我为什么会收到这个消息，该如何修复？

- dagwood

---

psUtil 的最后一个代码块有一段合法但看起来很奇怪的代码 if(it == vis.end()); else continue;。你真的是想要 if(it != vis.end()) continue; 吗？ - Michael Veksler

很可能是访问了向量中一个越界的位置，从而触发了未定义的行为。你可以使用编译器标志来捕捉它（clang++有sanitizer，Visual C++对容器有调试模式，G++使用-D_GLIBCXX_DEBUG启用调试模式）。另外，你可以用vector::at()方法替换所有使用vector::operator[]的地方，这样会更早地捕捉到问题。 - Michael Veksler

为什么我会收到这个消息，如何修复它？-- 在本地调试您的代码。只需创建一个“main”函数并添加测试数据即可。 - PaulMcKenzie

if(mat[x1][y1] <= mat[x][y]) -- Change that to if(mat.at(x1).at(y1) <= mat.at(x).at(y)) - PaulMcKenzie

Answer 1

我找到了我的错误！它是由于新计算出的坐标缺少边界检查和在psUtil开头的一个坐标不当的边界检查引起的。

改为这样：

if(x == m || y == n)
.
.
.
if(x1 < 0 || y1 < 0) continue; 

应该是这样的：

if(x == m-1 || y == n-1)
.
.
.
if(x1 < 0 || y1 < 0 || x1 >= m || y1 >= n) continue;

- dagwood

Answer 2

你的方法很不错，但是也许我们可以稍微改进一下实现。这里有一个使用类似DFS方法的已接受解决方案。

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

    void depth_first_search(vector<vector<int>> &grid, vector<vector<bool>> &visited, int row, int col, int height) {
        if (row < 0 || row > grid.size() - 1 || col < 0 || col > grid[0].size() - 1 || visited[row][col])
            return;

        if (grid[row][col] < height)
            return;

        visited[row][col] = true;

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

    vector<vector<int>> pacificAtlantic(vector<vector<int>> &grid) {
        vector<vector<int>> water_flows;
        int row_length = grid.size();

        if (!row_length)
            return water_flows;

        int col_length = grid[0].size();

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

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

        for (int col = 0; col < col_length; col++) {
            depth_first_search(grid, pacific, 0, col, INT_MIN);
            depth_first_search(grid, 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;
    }
};

我也不确定这是否是太平洋大西洋水流问题的最有效算法。你可以查看讨论板。

---

参考资料

• 如需更多详细信息，请查看讨论板。那里有很多被接受的解决方案、解释、各种语言的高效算法以及时间/空间复杂度分析。

• 417. 太平洋大西洋水流问题

• 417. 太平洋大西洋水流问题 - 讨论

- Emma

---

如果您能解释一下您的方法，那就太好了。 - dagwood