HDU 1495 非常可乐（bfs）|POJ 3414 Pots(bfs+打印路径)
【摘要】 题目链接~~>
这个题很有意义，很久以前就注意她了，不知道怎么搜！开始我用 dfs 写，写完后样例倒是能过，但是自己测试了几组数据就卡了，调试了老半天还是不行，接下来想怎么剪枝，郁闷了很久，决定上网搜一下，一搜原来用广搜，回来又开始用...
这个题很有意义，很久以前就注意她了，不知道怎么搜！开始我用 dfs 写，写完后样例倒是能过，但是自己测试了几组数据就卡了，调试了老半天还是不行，接下来想怎么剪枝，郁闷了很久，决定上网搜一下，一搜原来用广搜
，回来又开始用广搜写，简单调试了一下 1A。以后做题一定要先想好要用什么方法，这种方法可行不,如果超时还不如不写，以后做题要慎重啊！
代码：
-
#include<stdio.h>
-
#include<string.h>
-
#include<queue>
-
using namespace std ;
-
int a,b,c,m;
-
int vis[100][100];//标记！！
-
struct zhang
-
{
-
int x,y,z,bu;
-
};
-
void bfs(int x)//倒水只有六种情况
-
{
-
queue<zhang>q;
-
zhang current,next;
-
memset(vis,0,sizeof(vis));
-
current.x=x;
-
current.y=0;
-
current.z=0;
-
current.bu=0;
-
q.push(current);
-
while(!q.empty())
-
{
-
current=q.front();
-
q.pop();
-
if(vis[current.y][current.z])
-
continue;
-
if(current.x>0&¤t.y<b)
-
{
-
if(current.x+current.y<=b)
-
{
-
next.x=0;next.y=current.x+current.y;
-
next.z=current.z;next.bu=current.bu+1;
-
if(next.x==next.y&&next.x*2==a)
-
{
-
m=next.bu;
-
return ;
-
}
-
else
-
q.push(next);
-
}
-
else{
-
next.x=current.x+current.y-b;
-
next.y=b;next.z=current.z;
-
next.bu=current.bu+1;
-
if(next.x==next.y&&next.x*2==a)
-
{
-
m=next.bu;
-
return ;
-
}
-
else
-
q.push(next);
-
}
-
}
-
if(current.x>0&¤t.z<c)
-
{
-
if(current.x+current.z<=c)
-
{
-
next.x=0;next.y=current.y;
-
next.z=current.x+current.z;
-
next.bu=current.bu+1;
-
if(next.x==next.y&&next.x*2==a)
-
{
-
m=next.bu;
-
return ;
-
}
-
else
-
q.push(next);
-
}
-
else
-
{
-
next.x=current.x+current.z-c;
-
next.y=current.y;next.z=c;
-
next.bu=current.bu+1;
-
if(next.x==next.y&&next.x*2==a)
-
{
-
m=next.bu;
-
return ;
-
}
-
else
-
q.push(next);
-
}
-
}
-
if(current.y>0)
-
{
-
next.x=current.x+current.y;
-
next.y=0;next.z=current.z;
-
next.bu=current.bu+1;
-
if(next.x==next.y&&next.x*2==a)
-
{
-
m=next.bu;
-
return ;
-
}
-
else
-
q.push(next);
-
}
-
if(current.y>0&¤t.z<c)
-
{
-
if(current.y+current.z<=c)
-
{
-
next.x=current.x;next.y=0;
-
next.z=current.y+current.z;
-
next.bu=current.bu+1;
-
if(next.x==next.y&&next.x*2==a)
-
{
-
m=next.bu;
-
return ;
-
}
-
else
-
q.push(next);
-
}
-
else
-
{
-
next.x=current.x;next.y=current.y+current.z-c;
-
next.z=c;next.bu=current.bu+1;
-
if(next.x==next.y&&next.x*2==a)
-
{
-
m=next.bu;
-
return ;
-
}
-
else
-
q.push(next);
-
}
-
}
-
if(current.z>0)
-
{
-
next.x=current.x+current.z;
-
next.y=current.y;next.z=0;
-
next.bu=current.bu+1;
-
if(next.x==next.y&&next.x*2==a)
-
{
-
m=next.bu;
-
return ;
-
}
-
else
-
q.push(next);
-
}
-
if(current.z>0&¤t.y<b)
-
{
-
if(current.z+current.y<=b)
-
{
-
next.x=current.x;next.y=current.z+current.y;
-
next.z=0;next.bu=current.bu+1;
-
if(next.x==next.y&&next.x*2==a)
-
{
-
m=next.bu;
-
return ;
-
}
-
else
-
q.push(next);
-
}
-
else {
-
next.x=current.x;
-
next.y=b;next.z=current.z+current.y-b;
-
next.bu=current.bu+1;
-
if(next.x==next.y&&next.x*2==a)
-
{
-
m=next.bu;
-
return ;
-
}
-
else
-
q.push(next);
-
}
-
}
-
vis[current.y][current.z]=1;
-
}
-
}
-
int main()
-
{
-
while(scanf("%d%d%d",&a,&b,&c)!=EOF)
-
{
-
if(a==0&&b==0&&c==0)
-
break;
-
if(b==c)
-
{
-
printf("1\n");
-
continue;
-
}
-
if(a%2)
-
{
-
printf("NO\n");
-
continue;
-
}
-
m=-1;
-
int t;
-
if(b<c)
-
{
-
t=b;b=c;c=t;
-
}
-
bfs(a);
-
if(m!=-1)
-
printf("%d\n",m);
-
else
-
printf("NO\n");
-
}
-
return 0;
-
}
POJ 的 3414题 就多了一个打印路径。
代码：
-
#include<stdio.h>
-
#include<string.h>
-
#include<queue>
-
using namespace std ;
-
const int INF=100000 ;
-
int a,b,c ;
-
bool vis[105][105] ;
-
struct zhang
-
{
-
int x,y,z,step,pre ;
-
}q[INF] ;
-
void search(int x)
-
{
-
if(!x||x==1)
-
printf("FILL(%d)\n",x+1) ;
-
else if(x==2||x==3)
-
printf("DROP(%d)\n",x-1) ;
-
else if(x==4)
-
printf("POUR(1,2)\n") ;
-
else if(x==5)
-
printf("POUR(2,1)\n") ;
-
-
}
-
void print(int k)
-
{
-
if(k!=-1)
-
{
-
print(q[k].pre) ;
-
search(q[k].z) ;
-
}
-
return ;
-
}
-
int bfs(int x,int y)
-
{
-
int st=-1,head=0 ;
-
zhang curt,next ;
-
memset(vis,false,sizeof(vis)) ;
-
curt.x=x ;
-
curt.y=y ;
-
curt.z=-1 ;
-
curt.pre=-1 ;
-
curt.step=0 ;
-
vis[x][y]=true ;
-
q[++st]=curt ;
-
while(head<=st)
-
{
-
curt=q[head++] ;
-
if(curt.x==c||curt.y==c)
-
{
-
printf("%d\n",curt.step) ;
-
print(head-1) ;
-
return true ;
-
}
-
next.step=curt.step+1 ;
-
next.pre=head-1 ;
-
if(curt.x<a) //倒满A
-
{
-
next.x=a ;
-
next.y=curt.y ;
-
next.z=0 ;
-
if(!vis[next.x][next.y])
-
{
-
vis[next.x][next.y]=true ;
-
q[++st]=next ;
-
}
-
}
-
if(curt.y<b)//倒满B
-
{
-
next.x=curt.x ;
-
next.y=b ;
-
next.z=1 ;
-
if(!vis[next.x][next.y])
-
{
-
vis[next.x][next.y]=true ;
-
q[++st]=next ;
-
}
-
}
-
if(curt.x) // 倒掉A
-
{
-
next.x=0 ;
-
next.y=curt.y ;
-
next.z=2 ;
-
if(!vis[next.x][next.y])
-
{
-
vis[next.x][next.y]=true ;
-
q[++st]=next ;
-
}
-
}
-
if(curt.y)// 倒掉B
-
{
-
next.x=curt.x ;
-
next.y=0 ;
-
next.z=3 ;
-
if(!vis[next.x][next.y])
-
{
-
vis[next.x][next.y]=true ;
-
q[++st]=next ;
-
}
-
}
-
if(curt.x>0&&curt.y<b)// 从A 中向B 中倒水
-
{
-
next.z=4 ;
-
if(curt.x<=b-curt.y)
-
{
-
next.x=0 ;
-
next.y=curt.y+curt.x ;
-
if(!vis[next.x][next.y])
-
{
-
vis[next.x][next.y]=true ;
-
q[++st]=next ;
-
}
-
}
-
else
-
{
-
next.x=curt.x+curt.y-b ;
-
next.y=b ;
-
if(!vis[next.x][next.y])
-
{
-
vis[next.x][next.y]=true ;
-
q[++st]=next ;
-
}
-
}
-
}
-
if(curt.x<a&&curt.y>0)// 从B 中向A 中倒水
-
{
-
next.z=5 ;
-
if(curt.y<=a-curt.x)
-
{
-
next.x=curt.x+curt.y ;
-
next.y=0 ;
-
if(!vis[next.x][next.y])
-
{
-
vis[next.x][next.y]=true ;
-
q[++st]=next ;
-
}
-
}
-
else
-
{
-
next.x=a ;
-
next.y=curt.y+curt.x-a ;
-
if(!vis[next.x][next.y])
-
{
-
vis[next.x][next.y]=true ;
-
q[++st]=next ;
-
}
-
}
-
}
-
}
-
return false ;
-
}
-
int main()
-
{
-
while(scanf("%d%d%d",&a,&b,&c)!=EOF)
-
{
-
if(!bfs(0,0))
-
printf("impossible\n") ;
-
}
-
}
文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nyist_zxp/article/details/9717983
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）