本文主要是介绍poj 3414 dfs 广度优先搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给定两个杯子的容量a，b和目标水量c 。
有六种操作：
1、倒满a杯子。
2、倒满b杯子。
3、将a杯子的水全部倒出。
4、将b杯子的水全部倒出。
5、将a杯子的水倒到b杯子，直到a杯子倒尽或b杯子倒满。
6、将b杯子的水倒到a杯子，直到b杯子倒尽活a杯子倒满。
求：最少进行多少次操作使a或b任意一杯子的水量恰好等于目标水量c，并输出倒水的过程。
题目链接：http://poj.org/problem?id=3414
求解思路：6入口的BFS，记录每一次操作的前一次操作，当恰好找到目标状态的时候，从末尾找到初始状态输出。
#include<stdio.h>
#include<cstring>
#include<iostream>
#include<cstring>
using namespace std;
struct State
{int post;int a,b;int step;char d[10];
}state[10010];
int haha[10010];
int A,B,C;
bool visit[105][105];//标记该状态时否被访问过
int BFS()
{int head=0,tail=0;visit[0][0]=true;state[tail].a=0;state[tail].b=0;state[tail].step=0;state[tail].post=-2;tail++;while(1){State x=state[head];//cout<<state[head].a<<"*"<<state[head].b<<endl;if(head==tail){return -1;//队列为空，找不到.}if(x.a==C||x.b==C){return head;}if(!visit[A][x.b])// fill A;{visit[A][x.b]=true;state[tail].b=x.b;//这地方不要忘了记录，wa了好久state[tail].a=A;state[tail].post=head;strcpy(state[tail].d,"FILL(1)");state[tail++].step=x.step+1;}if(!visit[x.a][B]) //fill B{visit[x.a][B]=true;state[tail].a=x.a;state[tail].b=B;state[tail].post=head;strcpy(state[tail].d,"FILL(2)");state[tail++].step=x.step+1;}if(x.a+x.b<=B) //pour(a,b){if(!visit[0][x.a+x.b]){visit[0][x.a+x.b]=true;state[tail].b=x.a+x.b;state[tail].a=0;state[tail].post=head;strcpy(state[tail].d,"POUR(1,2)");state[tail++].step=x.step+1;}}else{if(!visit[x.a-(B-x.b)][B]){visit[x.a-(B-x.b)][B]=true;state[tail].a=x.a-(B-x.b);state[tail].b=B;state[tail].post=head;strcpy(state[tail].d,"POUR(1,2)");state[tail++].step=x.step+1;}}if(x.b+x.a<=A) //pour(b,a);{if(!visit[x.a+x.b][0]){visit[x.a+x.b][0]=true;state[tail].a=x.a+x.b;state[tail].step=x.step+1;state[tail].post=head;strcpy(state[tail].d,"POUR(2,1)");state[tail++].b=0;}}else{if(!visit[A][x.b-(A-x.a)]){visit[A][x.b-(A-x.a)]=true;state[tail].b=x.b-(A-x.a);state[tail].a=A;state[tail].post=head;strcpy(state[tail].d,"POUR(2,1)");state[tail++].step=x.step+1;}}if(!visit[0][x.b]) //drop A{visit[0][x.b]=true;state[tail].a=0;state[tail].b=x.b;state[tail].post=head;strcpy(state[tail].d,"DROP(1)");state[tail++].step=x.step+1;}if(!visit[x.a][0]) //drop B{visit[x.a][0]=true;state[tail].b=0;state[tail].a=x.a;state[tail].post=head;strcpy(state[tail].d,"DROP(2)");state[tail++].step=x.step+1;}head++;}
}
int main()
{while(scanf("%d%d%d",&A,&B,&C)!=EOF){memset(visit,false,sizeof(visit));int t=BFS();if(t==-1)printf("impossible\n");else{int i=0;while(state[t].post!=-2){haha[i]=t;i++;t=state[t].post;}cout<<i<<endl;for(int j=i-1;j>=0;j--){cout<<state[haha[j]].d<<endl;}}}return 0;这篇关于poj 3414 dfs 广度优先搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
