POJ 3414--Pots--BFS+回溯路徑

POJ 3414--Pots--BFS+回溯路徑

Pots Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 9963 Accepted: 4179 Special Judge

Description

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.

Input

On the first and only line are the numbers A, B, and C. These are all integers in the range from 1 to 100 and C≤max(A,B).

Output

The first line of the output must contain the length of the sequence of operations K. The following K lines must each describe one operation. If there are several sequences of minimal length, output any one of them. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’.

Sample Input

3 5 4

Sample Output

6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)

和之前做過的一道二維bfs一樣，只不過這個需要回溯路徑，很簡單在結構體中加一個變量來記錄上一個狀態在隊列中的下標（手敲的隊列比較好，這個時候在用STL隊列好像不大方便）最後找到滿足條件的狀態逆向打印路徑（因為記錄的都是上一個狀態）

#include 
#include 
#include 
#include 
#include 
using namespace std;
int m,n,c,s,e,p;
typedef struct node
{
	int v1,v2,cur,pre,op;
};
bool vis[999][999];
int ans[10010];
node que[10010];
void bfs()
{
	p=0;s=0;e=0;int pos;
	node t={0,0,0,0,0};
	que[e++]=t;
	vis[0][0]=1;
	while(s=0;i--)
			{
				switch(ans[i])
				{
					case 1:printf("FILL(1)\n");break;
					case 2:printf("FILL(2)\n");break;
					case 3:printf("DROP(1)\n");break;
					case 4:printf("DROP(2)\n");break;
					case 5:printf("POUR(2,1)\n");break;
					case 6:printf("POUR(1,2)\n");break;
				}
			}
			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;
			 t.cur=1;
			 t.pre=pos;
			 que[e++]=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;
			 t.cur=2;
			t.pre=pos;
			 que[e++]=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;
			 t.cur=3;
			 t.pre=pos;
			 que[e++]=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;
			 t.cur=4;
			 t.pre=pos;
			 que[e++]=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;
			 t.cur=5;
			 t.pre=pos;
			 que[e++]=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;
			 t.cur=6;
			 t.pre=pos;
			 que[e++]=t;
			}
		}
	}
	puts("impossible");
}
int main()
{
	while(cin>>m>>n>>c)
	{
		memset(vis,0,sizeof(vis));
		bfs();
	}
	return 0;
}