http://poj.org/problem?id=3414
这是一个广搜的题目,不难,就是有些许麻烦。对于练习还是个不错的题目。
题意就是给你两个杯子,这两个杯子的容量分别为a和b,要你通过一些操作,量出c那么多的水来。
fill就是填满那个杯子。无论杯子是否油水
prou(2,1)就是从第二个杯子向第一个杯子里倒水,当第一个满了或者第二个杯子是空的为止。
drop就是把这个杯子里的水都给倒掉。
#include <cstdio>
#include <iostream>
#include <string>
#include <string.h>
#include <queue> using namespace std; #define judge(x,y) x>=0&&y>=0&&x<=a&&y<=b&&mark[x][y] //一个判断,也是减少代码量,虽然我这个代码写的还是比较渣,很多东西都要一个一个些。其实完全可以套用模板来搞。
int a,b,c,flog; struct note{
int x,y,step,pos,i; //step记录当前的步数,pos记录上一步。然后可以进行回溯吧。
char str[]; //进行储存这一步的具体操作。
}; bool mark[][]; //代表这个点是否以前出现过。 char ans[][];
queue<note>s; void bfs(int x,int y)
{
note p[],q;
while(!s.empty())
s.pop();
strcpy(p[].str,"ssss"); //我这个目的完全是为了然s不为空的,因为如果p[0]没有值的话,p[0]是进不了队列的。
p[].pos=,p[].x=,p[].y=,p[].step=,p[].i=;
s.push(p[]);
int k=;
while(!s.empty())
{
q=s.front();
s.pop();
if(q.x==c||q.y==c){ //当量出了那么多的水的时候,就输出答案。
flog=; //这个是为了确定找到了答案。
printf("%d\n",q.step); //
int m=;
strcpy(ans[m],q.str);
m++;
for(int i=q.pos;i!=;) //回溯步骤。
{
strcpy(ans[m],p[i].str);
m++;
i=p[i].pos;
}
while(m--) //倒叙输出答案。
printf("%s\n",ans[m]);
return ;
}
if(judge(a,q.y))
{
p[++k].x=a;
p[k].y=q.y;
p[k].pos=q.i;
p[k].i=k;
strcpy(p[k].str,"FILL(1)");
mark[a][q.y]=false;
p[k].step=q.step+;
s.push(p[k]);
}
if(judge(q.x,b))
{
p[++k].x=q.x;
p[k].y=b;
p[k].pos=q.i;
p[k].i=k;
strcpy(p[k].str,"FILL(2)");
mark[q.x][b]=false;
p[k].step=q.step+;
s.push(p[k]);
}
if(judge(,q.y))
{
p[++k].x=;
p[k].y=q.y;
p[k].pos=q.i;
p[k].i=k;
strcpy(p[k].str,"DROP(1)");
mark[][q.y]=false;
p[k].step=q.step+;
s.push(p[k]);
}
if(judge(q.x,))
{
p[++k].x=q.x;
p[k].y=;
p[k].pos=q.i;
p[k].i=k;
strcpy(p[k].str,"DROP(2)");
mark[q.x][]=false;
p[k].step=q.step+;
s.push(p[k]);
}
if(q.x+q.y>=a&&judge(a,q.y+q.x-a))
{
p[++k].x=a;
p[k].y=q.y+q.x-a;
p[k].pos=q.i;
p[k].i=k;
strcpy(p[k].str,"POUR(2,1)");
mark[a][q.x+q.y-a]=false;
p[k].step=q.step+;
s.push(p[k]);
}
if(q.x+q.y<a&&judge(q.x+q.y,))
{
p[++k].x=q.x+q.y;
p[k].y=;
p[k].pos=q.i;
p[k].i=k;
strcpy(p[k].str,"POUR(2,1)");
mark[q.x+q.y][]=false;
p[k].step=q.step+;
s.push(p[k]);
}
if(q.x+q.y>=b&&judge(q.x+q.y-b,b))
{
p[++k].x=q.x+q.y-b;
p[k].y=b;
p[k].pos=q.i;
p[k].i=k;
strcpy(p[k].str,"POUR(1,2)");
mark[q.x+q.y-b][b]=false;
p[k].step=q.step+;
s.push(p[k]);
}
if(q.x+q.y<b&&judge(,q.x+q.y))
{
p[++k].x=;
p[k].y=q.x+q.y;
p[k].pos=q.i;
p[k].i=k;
strcpy(p[k].str,"POUR(1,2)");
mark[][q.x+q.y]=false;
p[k].step=q.step+;
s.push(p[k]);
}
}
} int main()
{
while(scanf("%d%d%d",&a,&b,&c)!=EOF)
{
flog=;
memset(mark,true,sizeof(mark));
bfs(,);
if(!flog) printf("impossible\n");
}
return ;
}