为什么即使在声明向量大小后仍会出现运行时错误？

Question

我正在解决 leetcode 问题：https://leetcode.com/problems/number-of-islands/

它给我这个错误：

Char 34: runtime error: addition of unsigned offset to 0x6080000000a0 overflowed to 0x60800000008c (stl_vector.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_vector.h:1043:34

我的代码：

class Solution {
public:
    void bfs(vector<int>&visited,vector<vector<char>>& grid,int r,int c,int n,int m)
    {
        queue<pair<int,int>>q;
        q.push({r,c});
        int dx[4]={1,-1,0,0};
        int dy[4]={0,0,1,-1};
        
        visited[r*m+c]=1;
        while(!q.empty())
        {   
            int x=q.front().first;
            int y=q.front().second;
            q.pop();
            for(int i=0;i<4;i++)
            {
                int newX=x+dx[i];
                int newY=y+dy[i];
                if(newX<n && newY<m && visited[newX*m+newY]==-1 && grid[newX][newY]=='1')
                {
                    q.push({newX,newY});
                    visited[newX*m+newY]=1;
                }
                    
            }
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        int n=grid.size();
        int m=grid[0].size();
        
        vector<int>visited(n*m+1,-1);
        
        int cnt=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(visited[i*m+j]==-1 && grid[i][j]=='1')
                {
                    bfs(visited,grid,i,j,n,m);
                   cnt++;
                }
            }
        }
        return cnt;
    }
};

我这里用到了BFS算法。我已经声明了所有向量的大小以防止越界错误，它仍然会发生。

Answer 1

这一行：

if(newX<n && newY<m && visited[newX*m+newY]==-1 && grid[newX][newY]=='1')

您永远不会检查 newX 或 newY 是否小于 0。如果是，访问 grid[newX][newY] 会出现运行时错误。

只需添加两个条件，如下图：

if(newX<n && newY<m && newX >= 0 && newY >= 0 && visited[newX*m+newY]==-1 && grid[newX][newY]=='1')

为什么即使在声明向量大小后仍会出现运行时错误？

Why getting runtime-error even after declaring size of vector?

c++

graph

runtime-error

c++14

breadth-first-search