首页 > 代码库 > poj3414（bfs）
poj3414（bfs）
题目链接：http://poj.org/problem?id=3414
题意：给你两个容器 A B 问是否能够经过有限的步骤倒水,得到容量为 C 的水，输出最小的步数,同时输出每一步的操作。如果不能达到目标状态,则输出 impossible。
分析：这题跟hdu1495一样，需要分情况考虑，不过这里回溯输出路径。。。
具体分析情况看这里：http://www.tuicool.com/articles/fqeI3i
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 100010using namespace std;int a,b,c;int ok,vis[110][110];struct node{ int x,y; int step;};struct point{ int x,y,op;}pre[110][110];node make_node(int a,int b,int c){ node temp; temp.x=a;temp.y=b;temp.step=c; return temp;}void path(int x,int y){ if(x+y==0) { return ; } path(pre[x][y].x,pre[x][y].y); if(pre[x][y].op==1) { printf("FILL(1)\n"); return; } if(pre[x][y].op==2) { printf("FILL(2)\n"); return; } if(pre[x][y].op==3) { printf("DROP(1)\n"); return; } if(pre[x][y].op==4) { printf("DROP(2)\n"); return; } if(pre[x][y].op==5) { printf("POUR(2,1)\n"); return; } if(pre[x][y].op==6) { printf("POUR(1,2)\n"); return; }}void bfs(){ queue<node>que; while(!que.empty())que.pop(); memset(vis,0,sizeof(vis)); memset(pre,0,sizeof(pre)); node cur,nxt; vis[0][0]=1; que.push(make_node(0,0,0)); while(!que.empty()) { cur=que.front();que.pop(); if(cur.x==c||cur.y==c) { printf("%d\n",cur.step); path(cur.x,cur.y);ok=1; return; }//printf("%d %d\n",cur.x,cur.y); if(!vis[a][cur.y]) { vis[a][cur.y]=1; pre[a][cur.y].x=cur.x; pre[a][cur.y].y=cur.y; pre[a][cur.y].op=1; que.push(make_node(a,cur.y,cur.step+1)); } if(!vis[cur.x][b]) { vis[cur.x][b]=1; pre[cur.x][b].x=cur.x; pre[cur.x][b].y=cur.y; pre[cur.x][b].op=2; que.push(make_node(cur.x,b,cur.step+1)); } if(!vis[0][cur.y]) { vis[0][cur.y]=1; pre[0][cur.y].x=cur.x; pre[0][cur.y].y=cur.y; pre[0][cur.y].op=3; que.push(make_node(0,cur.y,cur.step+1)); } if(!vis[cur.x][0]) { vis[cur.x][0]=1; pre[cur.x][0].x=cur.x; pre[cur.x][0].y=cur.y; pre[cur.x][0].op=4; que.push(make_node(cur.x,0,cur.step+1)); } if(cur.x+cur.y<=a) { int xx=cur.x+cur.y,yy=0; if(!vis[xx][yy]) { vis[xx][yy]=1; pre[xx][yy].x=cur.x; pre[xx][yy].y=cur.y; pre[xx][yy].op=5; que.push(make_node(xx,yy,cur.step+1)); } } else { int xx=a,yy=cur.x+cur.y-a; if(!vis[xx][yy]) { vis[xx][yy]=1; pre[xx][yy].x=cur.x; pre[xx][yy].y=cur.y; pre[xx][yy].op=5; que.push(make_node(xx,yy,cur.step+1)); } } if(cur.x+cur.y<=b) { int xx=0,yy=cur.x+cur.y; if(!vis[xx][yy]) { vis[xx][yy]=1; pre[xx][yy].x=cur.x; pre[xx][yy].y=cur.y; pre[xx][yy].op=6; que.push(make_node(xx,yy,cur.step+1)); } } else { int xx=cur.x+cur.y-b,yy=b; if(!vis[xx][yy]) { vis[xx][yy]=1; pre[xx][yy].x=cur.x; pre[xx][yy].y=cur.y; pre[xx][yy].op=6; que.push(make_node(xx,yy,cur.step+1)); } } }}int main(){ while(scanf("%d%d%d",&a,&b,&c)>0) { ok=0; bfs(); if(ok==0)puts("impossible"); }}
poj3414（bfs）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。