You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:

 

FILL(i)        fill the pot i (1 ≤ i ≤ 2) from the tap;

DROP(i)      empty the pot i to the drain;

POUR(i,j)    pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).

Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.

POUR(2,1)

DROP(1)

POUR(2,1)

FILL(2)

POUR(2,1)

简单搜索题，对于两个空瓶子，容积分别为A B 有6种操作 把A（或B）清空，把A（或B）装满，把A倒入B，把B倒入A 。相应这6种操作，有6种状态。典型的bfs搜索。不多了，仅仅是这题明明说的是单组输入结果答案却要多组输入才对。白白贡献5个WA。

#include <cstdio>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <queue>

using namespace std;

int m,n,c;

typedef struct node

{

	int v1,v2,op;

};

bool vis[999][999];

void bfs()

{

	node t={0,0,0};

	queue <node> Q;

	Q.push(t);

	vis[0][0]=1;

	while(!Q.empty())

	{

		node f=Q.front();Q.pop();

		if(f.v1==c||f.v2==c)

		{

			cout<<f.op<<endl;

			return ;

		}

		if(f.v1!=m)

		{

			t.v1=m;

			t.op=f.op+1;

			t.v2=f.v2;

			if(!vis[t.v1][t.v2])

			{

			 vis[t.v1][t.v2]=1;

			 Q.push(t);

			}

		}

		if(f.v2!=n)

		{

			t.v2=n;

			t.op=f.op+1;

			t.v1=f.v1;

			if(!vis[t.v1][t.v2])

			{

			 vis[t.v1][t.v2]=1;

			 Q.push(t);

			}

		}

		if(f.v1!=0)

		{

			t.v1=0;

			t.v2=f.v2;

			t.op=f.op+1;

			if(!vis[t.v1][t.v2])

			{

			 vis[t.v1][t.v2]=1;

			 Q.push(t);

			}

		}

		if(f.v2!=0)

		{

			t.v2=0;

			t.v1=f.v1;

			t.op=f.op+1;

			if(!vis[t.v1][t.v2])

			{

			 vis[t.v1][t.v2]=1;

			 Q.push(t);

			}

		}

		if(f.v2!=0&&f.v1!=m)

		{

			t.v2=f.v2-(m-f.v1);if(t.v2<0) t.v2=0;

			t.v1=f.v1+f.v2;  if(t.v1>m) t.v1=m;

			t.op=f.op+1;

			if(!vis[t.v1][t.v2])

			{

			 vis[t.v1][t.v2]=1;

			 Q.push(t);

			}

		}

		if(f.v1!=0&&f.v2!=n)

		{

			t.v1=f.v1-(n-f.v2);if(t.v1<0) t.v1=0;

			t.v2=f.v2+f.v1;  if(t.v2>n) t.v2=n;

			t.op=f.op+1;

			if(!vis[t.v1][t.v2])

			{

			 vis[t.v1][t.v2]=1;

			 Q.push(t);

			}

		}

	}

	puts("impossible");

}

int main()

{

	while(cin>>m>>n>>c)

	{

		memset(vis,0,sizeof(vis));

		bfs();

	}

	return 0;

}