0

bad_alloc error coming. What is the reason? Code is trying to find a path from a given starting point to a destination point without moving over X and moving only horizontally and vertically. Question is present on hackerrank under data-structures->queue named Castle on the grid.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;


int main() {
    int N;
    cin>>N;
    string s[N];
    for(int i=0;i<N;i++)
        cin>>s[i];
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    queue<int> x,y,dist,h;
    int v[N][N];
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++)
            v[i][j]=0;
    }
    v[a][b]=1;
    if(b-1>=0 && s[a][b-1]!='X'){
        x.push(a);
        y.push(b-1);
        h.push(1);
        dist.push(1);
    }
    if(b+1<N && s[a][b+1]!='X'){
        x.push(a);
        y.push(b+1);
        h.push(1);
        dist.push(1);
    }
    if(a-1>=0 && s[a-1][b]!='X'){
        x.push(a-1);
        y.push(b);
        h.push(0);
        dist.push(1);
    }
    if(a+1<N && s[a+1][b]!='X'){
        x.push(a+1);
        y.push(b);
        h.push(0);
        dist.push(1);
    }
    int minSteps=1000000000;
    while(!x.empty()){
        int cx=x.front();
        int cy=y.front();
        int h1=h.front();
        int d1=dist.front();
        v[cx][cy]=1;
        x.pop();y.pop();
        h.pop();dist.pop();
        if(cx==c && cy==d){
            if(d1<minSteps)
                minSteps=d1;
        }
        else{
            if(cy-1>=0 && v[cx][cy-1]==0 && s[cx][cy-1]!='X'){
                x.push(cx);
                y.push(cy-1);
                if(h1==0)
                    dist.push(d1+1);
                else
                    dist.push(d1);
                h.push(1);
            }
            if(cy+1<N && v[cx][cy+1]==0 && s[cx][cy+1]!='X'){
                x.push(cx);
                y.push(cy+1);
                if(h1==0)
                    dist.push(d1+1);
                else
                    dist.push(d1);
                h.push(1);
            }
            if(cx-1>=0 && v[cx-1][cy]==0 && s[cx-1][cy]!='X'){
                x.push(cx-1);
                y.push(cy);
                if(h1==1)
                    dist.push(d1+1);
                else
                    dist.push(d1);
                h.push(0);
            }
            if(cx+1<N && v[cx+1][cy]==0 && s[cx+1][cy]!='X'){
                x.push(cx+1);
                y.push(cy);
                if(h1==1)
                    dist.push(d1+1);
                else
                    dist.push(d1);
                h.push(0);
            }
        }
    }
    cout<<minSteps<<endl;
    return 0;
}
Sourabh
  • 1
  • 1
    First of all, what is the input, most importantly, the value of `N`? Secondly, use a debugger to catch the exception and locate where it happens. Thirdly, your program is technically not a valid C++ programs, because C++ doesn't have [variable-length arrays](https://en.wikipedia.org/wiki/Variable-length_array). Use `std::vector` instead (and depending on the value of `N` it might even solve your problem). – Some programmer dude Apr 01 '17 at 13:57
  • In the while loop, depending on the values of various variables, you could have up to 4 pushes for each pop. That would of course eventually lead to all memory being consumed. – Bo Persson Apr 01 '17 at 14:02
  • if you declare your array of string's like this `string s[N];`, N must be constant witch is not the case in your code. – HDJEMAI Apr 01 '17 at 15:05

0 Answers0