博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
pots(bfs)
阅读量:5286 次
发布时间:2019-06-14

本文共 2606 字,大约阅读时间需要 8 分钟。

#include 
#include
#include
using namespace std;int A,B,C,vis[101][101];char str[6][10] = {
"FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"};structnode{
int num,a,b; node *pre;};node que[101*101];void print(node now){
if (now.pre) {
print(*now.pre); printf("%s\n",str[now.num]); }}void BFS(){
int step=0,head=0,tail=1,count,water1,water2; que[0].a=que[0].b=0; que[0].pre=0; while (tail-head>0) {
count=tail-head; while (count--) {
node now=que[head]; if (now.a==C || now.b==C) {
printf("%d\n",step); print(now); return; } if(!vis[A][now.b]) {
vis[A][now.b]=1; que[tail].num=0; que[tail].a=A; que[tail].b=now.b; que[tail++].pre=&que[head]; } if(!vis[now.a][B]) {
vis[now.a][B]=1; que[tail].num=1; que[tail].a=now.a; que[tail].b=B; que[tail++].pre=&que[head]; } if(!vis[0][now.b]) {
vis[A][now.b]=1; que[tail].num=2; que[tail].a=0; que[tail].b=now.b; que[tail++].pre=&que[head]; } if(!vis[now.a][0]) {
vis[now.a][0]=1; que[tail].num=3; que[tail].a=now.a; que[tail].b=0; que[tail++].pre=&que[head]; } water1=min (now.a,B-now.b); if(!vis[now.a-water1][now.b+water1]) {
vis[now.a-water1][now.b+water1]=1; que[tail].num=4; que[tail].a=now.a-water1; que[tail].b=now.b+water1; que[tail++].pre=&que[head]; } water2=min (A-now.a,now.b); if(!vis[now.a+water2][now.b-water2]) {
vis[now.a+water2][now.b-water2]=1; que[tail].num=5; que[tail].a=now.a+water2; que[tail].b=now.b-water2; que[tail++].pre=&que[head]; } head++; } step++; } printf("impossible\n");}int main (){
scanf("%d%d%d",&A,&B,&C); memset(vis,0,sizeof(vis)); vis[0][0]=1; BFS(); return 0;}

转载于:https://www.cnblogs.com/You-Change/p/3465937.html

你可能感兴趣的文章
配置EditPlus使其可以编译运行java程序
查看>>
java中的占位符\t\n\r\f
查看>>
MySQL通过frm 和 ibd 恢复数据过程
查看>>
SRS源码——Listener
查看>>
Java面向对象抽象类案例分析
查看>>
对SPI、IIC、IIS、UART、CAN、SDIO、GPIO的解释
查看>>
Thymeleaf模板格式化LocalDatetime时间格式
查看>>
庖丁解“学生信息管理系统”
查看>>
Pyltp使用
查看>>
其他ip无法访问Yii的gii,配置ip就可以
查看>>
php做的一个简易爬虫
查看>>
x的x次幂的值为10,求x的近似值
查看>>
jquery获取html元素的绝对位置和相对位置的方法
查看>>
ios中webservice报文的拼接
查看>>
Power BI 报告的评论服务支持移动设备
查看>>
ACdream 1068
查看>>
HDU 2665 Kth number
查看>>
记叙在人生路上对你影响最大的三位老师
查看>>
002.大数据第二天
查看>>
python装饰器
查看>>