罐子Pots - POJ 3414 (BFS)
题目是给你两个杯子A,B。一开始为空，输入一个目标C。找到通过6种操作让A,或者B到达C的大小的最少操作流程,倒满A或者B，倒掉A或者B,从A倒到B,从B倒到A,如果没有最短路径就输出'impossible'。
最少操作流程
通过对六种操作方法的模拟
输入
输入
3 5 4输出
6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)很简单的一道搜索题，算是入门题目。
1.BFS求最少操作
模拟六种操作
2.用数组模拟队列
用一个last储存上一次操作
最后用递归得出结果
#include<iostream>
using namespace std;
bool book[105][105];//标记数组，看A,B的状态是不是走过了
struct node
{
int x,y;
int w;
int step;
int last;
string answ;
}tu[100005];//路径数组
void print(int w)//递归打印路径
{
if(w==-1)return;
else
{
print(tu[w].last);if(tu[w].w==0)printf("FILL(1)\n");
else if(tu[w].w==1)printf("FILL(2)\n");
else if(tu[w].w==2)printf("DROP(1)\n");
else if(tu[w].w==3)printf("DROP(2)\n");
else if(tu[w].w==4)printf("POUR(1,2)\n");
else if(tu[w].w==5)printf("POUR(2,1)\n");
}
}
int main()
{
int a,b,c;
cin>>a>>b>>c;//BFS
int head;
int tail;
head=tail=0;tu[head].x=0;
tu[head].y=0;
tu[head].w=-1;
tu[head].last=-1;
tu[head].step=0;
tail++;
book[0][0]=1;
int flag=0;
while(head<tail)
{
int ux=tu[head].x;
int uy=tu[head].y;if(ux==c||uy==c)
{
cout<<tu[head].step<<endl;
print(tu[head].last);if(tu[head].w==0)printf("FILL(1)\n");
else if(tu[head].w==1)printf("FILL(2)\n");
else if(tu[head].w==2)printf("DROP(1)\n");
else if(tu[head].w==3)printf("DROP(2)\n");
else if(tu[head].w==4)printf("POUR(1,2)\n");
else if(tu[head].w==5)printf("POUR(2,1)\n");
flag=1;
break;
}
head++;
for(int i=0;i<6;i++)//1to6是模拟各种状态
{
if(i==0&&!book[a][uy]&&ux!=a)
{
book[a][uy]=1;
tu[tail].x=a;
tu[tail].y=uy;
tu[tail].w=i;
tu[tail].step=tu[head-1].step+1;
tu[tail].last=head-1;
tail++;
}
if(i==1&&!book[ux][b]&&b!=uy)
{
book[ux][b]=1;
tu[tail].x=ux;
tu[tail].y=b;
tu[tail].w=i;
tu[tail].step=tu[head-1].step+1;
tu[tail].last=head-1;
tail++;
}
if(i==2&&!book[0][uy]&&ux!=0)
{
book[0][uy]=1;
tu[tail].x=0;
tu[tail].y=uy;
tu[tail].w=i;
tu[tail].step=tu[head-1].step+1;
tu[tail].last=head-1;
tail++;
}
if(i==3&&!book[ux][0]&&uy!=0)
{
book[ux][0]=1;
tu[tail].x=ux;
tu[tail].y=0;
tu[tail].w=i;
tu[tail].step=tu[head-1].step+1;
tu[tail].last=head-1;
tail++;
}
if(i==4)//min是求可不可以倒满，i==5也是
{
int u=min(ux,b-uy);
tu[tail].x=ux-u;
tu[tail].y=uy+u;
if(book[ux-u][uy+u])continue;book[ux-u][uy+u]=1;
tu[tail].w=i;
tu[tail].step=tu[head-1].step+1;
tu[tail].last=head-1;
tail++;
}
if(i==5)
{
int u=min(a-ux,uy);
tu[tail].x=ux+u;
tu[tail].y=uy-u;
if(book[ux+u][uy-u])continue;
book[ux+u][uy-u]=1;
tu[tail].w=i;
tu[tail].step=tu[head-1].step+1;
tu[tail].last=head-1;
tail++;
}
}
}if(!flag)cout<<"impossible"<<endl;
//有那么种情况是无法满足条件就可以输出imposible,用flag判断
}写的时候有一个bug就是我将
tu[tail].step=tu[head-1].step+1;
tu[tail].last=head-1;
tail++;写在for中的全部if后面，导致就是如果那个地方已经走过依旧会把这个状态压入队列，最后死循环runtime error，计算错误。
这个题算是bfs的一个状态模拟吧。还有一道类似的当比这个简单的题：J - 非常可乐
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-07-01，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读