I have tried to solve the problem using bfs. I get a time limit exceeded here. I have even eliminated the visited nodes by storing them in a hashmap ‘hm’. I have pasted the code.
`package s43;
import java.io.;
import java.util.;
public class s25 {
static Node left_possible(Node n1,int lmax,int rmax){
int inilv=n1.lv;
int inirv=n1.rv;
if(n1.lv==lmax)
{
n1.lv=0;
n1.parentlv=inilv;
n1.parentrv=inirv;
n1.level=n1.level+1;
return n1;
}
else if(n1.rv!=0)
{
n1.lv=n1.lv+n1.rv;
if(n1.lv>lmax)
n1.lv=lmax;
n1.rv=n1.rv-(lmax-inilv);
if(n1.rv<0)
n1.rv=0;
if(n1.lv==n1.parentlv && n1.rv==n1.parentrv)
{
n1.lv=lmax;
n1.rv=inirv;
n1.parentlv=inilv;
n1.parentrv=inirv;
n1.level=n1.level+1;
return n1;
}
n1.parentlv=inilv;
n1.parentrv=inirv;
n1.level=n1.level+1;
return n1;
}
else
{
n1.lv=lmax;
n1.parentlv=inilv;
n1.parentrv=inirv;
n1.level=n1.level+1;
return n1;
}
}
static Node right_possible(Node n1,int lmax,int rmax){
int inirv=n1.rv;
int inilv=n1.lv;
if(n1.rv==rmax)
{
n1.rv=0;
n1.parentlv=inilv;
n1.parentrv=inirv;
n1.level=n1.level+1;
return n1;
}
else if(n1.lv!=0)
{
n1.rv=n1.rv+n1.lv;
if(n1.rv>rmax)
n1.rv=rmax;
n1.lv=n1.lv-(rmax-inirv);
if(n1.lv<0)
n1.lv=0;
if(n1.lv==n1.parentlv && n1.rv==n1.parentrv)
{
n1.lv=inilv;
n1.rv=rmax;
n1.parentlv=inilv;
n1.parentrv=inirv;
n1.level=n1.level+1;
return n1;
}
n1.parentlv=inilv;
n1.parentrv=inirv;
n1.level=n1.level+1;
return n1;
}
else
{
n1.rv=rmax;
n1.parentlv=inilv;
n1.parentrv=inirv;
n1.level=n1.level+1;
return n1;
}
}
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
//long startTime = System.currentTimeMillis();
BufferedReader inp = new BufferedReader (new InputStreamReader(System.in));
String s;
int temp=0;
String[] b1;
StringBuilder fin=new StringBuilder();
HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>();
fin.append("");
int m=0;
s=inp.readLine();
b1=s.split(" ");
for(String ss : b1)
{
if(!ss.equals(""))
{
m=Integer.parseInt(ss);
break;
}
}
int a,b,c;
Queue<Node> q = new LinkedList<Node>();
for(int l=0;l<m;l++ )
{
a=0;b=0;c=0;
s=inp.readLine();
b1=s.split(" ");
for(String ss : b1)
{
if(!ss.equals(""))
{
a=Integer.parseInt(ss);
break;
}
}
s=inp.readLine();
b1=s.split(" ");
for(String ss : b1)
{
if(!ss.equals(""))
{
b=Integer.parseInt(ss);
break;
}
}
s=inp.readLine();
b1=s.split(" ");
for(String ss : b1)
{
if(!ss.equals(""))
{
c=Integer.parseInt(ss);
break;
}
}
Node n = new Node();
n.lv=0;
n.rv=0;
n.parentlv=0;
n.parentrv=0;
n.level=0;
q.add(n);
hm.put(0,0);
// int count=0;
int notpossible=0;
if(c>a && c>b)
notpossible=1;
if(a>b)
{
if(a%b==0 && c%b!=0)
notpossible=1;
}
if(a<b)
{
if(b%a==0 && c%a!=0)
notpossible=1;
}
if(c==0)
{
fin.append(0);
fin.append("\n");
continue;
}
if(c==a || c==b)
{
fin.append(1);
fin.append("\n");
continue;
}
Node n1=new Node();
while(notpossible==0)
{
n1=q.remove();
//count++;
if(n1.lv==c || n1.rv==c)
break;
Node nc1=new Node();
Node nc2=new Node();
nc1.copy(n1);
nc2.copy(n1);
Node nl,nr;
nl=left_possible(nc1,a,b);
nr=right_possible(nc2,a,b);
if(hm.containsKey(nl.lv))
{
if(hm.get(nl.lv)==nl.rv)
temp=1;
}
if(temp!=1)
{
hm.put(nl.lv, nl.rv);
q.add(nl);
}
temp=0;
if(hm.containsKey(nr.lv))
{
if(hm.get(nr.lv)==nr.rv)
temp=1;
}
if(temp!=1)
{
hm.put(nr.lv, nr.rv);
q.add(nr);
}
temp=0;
if(q.isEmpty())
{
notpossible=1;
break;
}
}
double sum=0;double i=0;
if(notpossible==1)
{
fin.append(-1);
fin.append("\n");
}
else
{
/* while(sum<count)
{
sum=sum+Math.pow(2, i);
i++;
}*/
// fin.append(Math.round(i-1));
fin.append(n1.level);
fin.append("\n");
}
hm.clear();
q.clear();
}
/*long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.println(elapsedTime);*/
System.out.println(fin);
}
}
class Node{
int lv; // contain the level of liquid in the left (lv) and right (rv) vessels
int rv;
int parentlv;
int parentrv;
int level;
public void copy(Node anothernode)
{
this.lv=anothernode.lv;
this.rv=anothernode.rv;
this.parentlv=anothernode.parentlv;
this.parentrv=anothernode.parentrv;
this.level=anothernode.level;
}
}
`
Any help will be appreciated. Thanks!