Question- https://www.spoj.com/problems/POUR1/
#include<bits/stdc++.h>
using namespace std;
#define MAX 100000000
int a,b,c;
int dp[40005][40005];
bool visited[40005][40005];
int dynamic(int,int);
int main()
{
int tc,i,j,temp;
cin>>tc;
for(i=0;i<tc;i++){
cin>>a>>b>>c;
if(c>a && c>b){
cout<<"-1"<<endl;
continue;
}
memset(dp,-1,sizeof dp);
memset(visited,false,sizeof visited);
visited[0][0]=true;
visited[a][0]=true;
temp=min(dynamic(0,b),dynamic(a,0));
if(temp>=MAX){
cout<<"-1"<<endl;
continue;
}
cout<<temp<<endl;
}
return 0;
}
int dynamic(int x,int y)
{
if(dp[x][y]!=-1)
return dp[x][y];
if(x==c || y==c){
dp[x][y]=1;
return dp[x][y];
}
int ans=MAX,temp,flag=0;
if(visited[0][y]==false){
visited[0][y]=true;
ans=1+dynamic(0,y);
flag=1;
}
if(visited[x][0]==false){
visited[x][0]=true;
temp=1+dynamic(x,0);
if(temp<ans)
ans=temp;
flag=1;
}
if(visited[a][y]==false){
visited[a][y]=true;
temp=1+dynamic(a,y);
if(temp<ans)
ans=temp;
flag=1;
}
if(visited[x][b]==false){
visited[x][b]=true;
temp=1+dynamic(x,b);
if(temp<ans)
ans=temp;
flag=1;
}
if(x+y>b && visited[x+y-b][b]==false){
visited[x+y-b][b]=true;
temp=1+dynamic(x+y-b,b);
if(temp<ans)
ans=temp;
flag=1;
}
else if(x+y<=b && visited[0][x+y]==false){
visited[0][x+y]=true;
temp=1+dynamic(0,x+y);
if(temp<ans)
ans=temp;
flag=1;
}
if(x+y>a && visited[a][x+y-a]==false){
visited[a][x+y-a]=true;
temp=1+dynamic(a,x+y-a);
if(temp<ans)
ans=temp;
flag=1;
}
else if(x+y<=a && visited[x+y][0]==false){
visited[x+y][0]=true;
temp=1+dynamic(x+y,0);
if(temp<ans)
ans=temp;
flag=1;
}
if(flag==0){
dp[x][y]=MAX;
return dp[x][y];
}
dp[x][y]=ans;
return dp[x][y];
}
I did this problem using dynamic programming. But here one problem is occuring. Declaring big 2d array is not possible. Otherwise solution is running perfectly.
What should i do to overcome this problem?