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')