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

Time:06-04

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.

CodePudding user response:

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] gives 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')
  • Related