Hello,
this is my solution to HIGHWAYBYPASS problem from INOI 2014 (prob 1) The statement here
The INOI online test server gives some six testcases from the first subtask correct while two exceed the memory limit (750 MiB). I am not able to figure out what is wrong. [Signal 11 SIGSEGV memory violation]
The strategy:
I have used BFS assuming the grid as a graph. For every ‘nextNode’ , if the nextNode is same as destination, you remove it from the queue and mark +1 to the total sum of paths.
I don’t know where it is going wrong and also can’t imagine for what kind of a test case the code is failing.
Please help out!
#include <iostream>
#include <queue>
#include <vector>
#define big unsigned long long int
#define vectud vector <vector <big> >
const int MOD=20011;
/* code */
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
vectud matrix;
big ry,cx,dmx;
big path=0;
int iter=0;
cin>>ry>>cx>>dmx;
for (big i=0; i<ry; i++)
{
vector <big> row;
for (big j=0; j<cx; j++)
{
big x;
cin>>x;
row.push_back(x);
}
matrix.push_back(row);
}
queue <big> x,y,dwn,rgt;
// x.clear(); y.clear(); dwn.clear(); rgt.clear();
x.push(0); y.push(0); dwn.push(0); rgt.push(0);
while (x.empty()==false && y.empty()==false)
{
iter++;
big xc=x.front(), yr=y.front();
// x.pop(); y.pop(); rgt.pop(); down.pop();
if (matrix[yr][xc]==0){
// x.pop(); y.pop(); rgt.pop(); dwn.pop();
// cout<<endl<<"empty"<<endl;
}
else if (yr==ry-1 && xc==cx-1)
{
// x.pop(); y.pop(); rgt.pop(); dwn.pop();
path+=1;
//cout<<endl<<"path++"<<endl;
}
else {
if (xc != cx-1 && rgt.front() != dmx)
{
// cout<<endl<<"if-1"<<"\n"<<endl;
x.push(xc+1);
rgt.push(rgt.front()+1);
y.push(yr);
dwn.push(0);
// x.pop(); y.pop(); rgt.pop(); dwn.pop();
}
if (yr != ry-1 && dwn.front() != dmx)
{
//cout<<endl<<"if-2"<<"\n"<<endl;
y.push(yr+1);
dwn.push(dwn.front()+1);
x.push(xc);
rgt.push(0);
// x.pop(); y.pop(); rgt.pop(); dwn.pop();
}
}
x.pop(); y.pop(); rgt.pop(); dwn.pop();
}
//cout<<endl<<iter<<endl<<endl<<endl;
long long int hula = path % MOD;
cout<<hula<<endl;
return 0;
}