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

Issue

I am solving leetcode problem : https://leetcode.com/problems/number-of-islands/

It gives me this error:

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

My code:

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;
    }
};

I have used the BFS algorithm here. I have declared sizes of all vectors to prevent out of bounds error, still its occuring.

Solution

In this line:

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

You never check if newX or newY are less than 0. If so, accessing grid[newX][newY] could give a runtime error.

Just add two conditions, as shown below:

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

Answered By - Ryan Zhang

Answer Checked By - Clifford M. (PHPFixing Volunteer)