http://poj.org/problem?id=3414
题意 ： 大意是说给你两个杯子的体积和一个目标体积，a,b,c，通过对a,b进行6种操作，调出c体积的水，6种操作分别是把a倒满，把b倒满，把a弄成空的，把b弄成空的，把a里边的倒到b里，把b里边的水倒到a里；
思路 ： 算不上说多难，反正就是六种操作
#include<cstdio>
#include<cstring>
#include<iostream>
const int maxn = ;
using namespace std;
int a,b,c;
int r,l;
int vis[][];
struct node
{
int cup1,cup2,step;//两个杯子,走的步数
int mark;//进行标记，方便输出
int prev;//记录前一个状态
}ch[maxn],sh,zh;
int stepp,s;
void bfs()
{
/*初始化*/
ch[].cup1 = ;
ch[].cup2 = ;
ch[].step = ;
ch[].mark = ;
l = ,r = ;
vis[][] = ;
/*队列模拟*/
while(l<r)
{
sh = ch[l] ;
if(sh.cup1 == c||sh.cup2 == c)//结束标志
{
stepp = sh.step ;
s = l ;//输出时寻找前驱的
return ;
}
if(sh.cup1 != a)//将杯1倒满
{
zh.cup1 = a ;
zh.cup2 = sh.cup2 ;
zh.step = sh.step+ ;
zh.prev = l ;
zh.mark = ;
if(!vis[zh.cup1][zh.cup2])
{
vis[zh.cup1][zh.cup2] = ;
ch[r++] = zh ;//这个状态存到ch数组里
}
}
if(sh.cup2 != b)//将杯2装满
{
zh.cup2 = b ;
zh.cup1 = sh.cup1 ;
zh.step = sh.step+ ;
zh.mark = ;
zh.prev = l;
if(!vis[zh.cup1][zh.cup2])
{
vis[zh.cup1][zh.cup2] = ;
ch[r++] = zh ;
}
}
if(sh.cup1 != )//将杯1倒空
{
zh.cup1 = ;
zh.cup2 = sh.cup2 ;
zh.mark = ;
zh.prev = l;
zh.step = sh.step+ ;
if(!vis[zh.cup1][zh.cup2])
{
vis[zh.cup1][zh.cup2] = ;
ch[r++] = zh ;
}
}
if(sh.cup2 != )//将杯2倒空
{
zh.cup2 = ;
zh.cup1 = sh.cup1;
zh.mark = ;
zh.prev = l;
zh.step = sh.step+ ;
if(!vis[zh.cup1][zh.cup2])
{
vis[zh.cup1][zh.cup2] = ;
ch[r++] = zh ;
}
}
if(sh.cup1 != )//将杯1水倒到杯2里
{
if(sh.cup1 >= b-sh.cup2)
{
zh.cup1 = sh.cup1-(b-sh.cup2) ;
zh.cup2 = b ;
}
else
{
zh.cup2 = sh.cup1+sh.cup2 ;
zh.cup1 = ;
}
zh.step = sh.step+ ;
zh.mark = ;
zh.prev = l ;
if(!vis[zh.cup1][zh.cup2])
{
vis[zh.cup1][zh.cup2] = ;
ch[r++] = zh ;
}
}
if(sh.cup2 != )//将杯2水倒到杯1里
{
if(sh.cup2 >= a-sh.cup1)
{
zh.cup2 = sh.cup2- (a-sh.cup1);
zh.cup1 = a ;
}
else
{
zh.cup1 = sh.cup1+sh.cup2 ;
zh.cup2 = ;
}
zh.step = sh.step+ ;
zh.mark = ;//进行标记
zh.prev = l ;
if(!vis[zh.cup1][zh.cup2])
{
vis[zh.cup1][zh.cup2] = ;
ch[r++] = zh ;
}
}
l++ ;
}
}
void printff(int i)
{
if(i == )
return ;
printff(ch[i].prev) ;
if(ch[i].mark == ) printf("FILL(1)\n");
else if(ch[i].mark == ) printf("FILL(2)\n");
else if(ch[i].mark == ) printf("DROP(1)\n");
else if(ch[i].mark == ) printf("DROP(2)\n");
else if(ch[i].mark == ) printf("POUR(1,2)\n");
else if(ch[i].mark==) printf("POUR(2,1)\n");
}
int main()
{
while(scanf("%d %d %d",&a,&b,&c)!=EOF)
{
stepp=;
memset(vis,,sizeof(vis));
bfs();
if(stepp != )
{
printf("%d\n",stepp);
printff(s);
}
else printf("impossible\n");
}
return ;
}