# INOI 2014 (problem#1) HIGHWAY BYPASS - problem difficulty

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.

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

The question was to find the number of ways to go from top left to bottom right. An exhaustive search like this would not work as the number of ways is pretty large for even small grids. This was a dynamic programming question till i know, that is how i solved it last year during INOI. Think on those lines.

Please give me a starting point.

Try solving the problem without the restriction in travelling in the same direction maybe. dp[i][j] as number of ways of coming from top left to (i,j)

guys i am having a problem of taking input. can somebody help. http://pastebin.com/cqqH8JRs

//