Pots（bfs+路径记录与回溯）

F - Pots

  POJ - 3414  其实是一道很经典但是看起来难，其实没那么难的一道bfs+路径回溯题目 bfs是基础，而对于路径回溯刚开始那么清楚，其实发现是一个很简单的问题标记路径就可以解决 #include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <algorithm> using namespace std; struct node { int x,y; int step; }st,ed; int a,b,c; int book[105][105]; int pre_x[105][105]; int pre_y[105][105]; char opr[][10]={"","DROP(1)","DROP(2)","FILL(1)","FILL(2)","POUR(1,2)","POUR(2,1)"}; int flag; void pri(int x,int y) { //printf("%d %d %d\n",book[x][y],x,y); if(book[x][y]==0||book[x][y]==-1) { return ; } pri(pre_x[x][y],pre_y[x][y]); printf("%s\n",opr[book[x][y]]); return ; } void bfs() { memset(book,0,sizeof(book)); memset(pre_x,0,sizeof(pre_x)); memset(pre_y,0,sizeof(pre_y)); st.x=0;st.y=0;st.step=0; book[st.x][st.y]=-1; queue<node>Q; Q.push(st); while(!Q.empty()) { st=Q.front(); Q.pop(); if(st.x==c||st.y==c) { flag=1; printf("%d\n",st.step); pri(st.x,st.y); return ; } for(int i=1;i<=6;i++) { if(i==1) { ed.x=0;ed.y=st.y; } if(i==2) { ed.x=st.x;ed.y=0; } if(i==3) { ed.x=a;ed.y=st.y; } if(i==4) { ed.x=st.x;ed.y=b; } if(i==5)//x->y { if(st.x<=b-st.y) { ed.x=0;ed.y=st.y+st.x; } else if(st.x>b-st.y) { ed.x=st.x-(b-st.y);ed.y=b; } } if(i==6)//y->x { if(a-st.x>=st.y) { ed.y=0;ed.x=st.y+st.x; } else if(a-st.x<st.y) { ed.x=a;ed.y=st.y-(a-st.x); } } ed.step=st.step+1; if(book[ed.x][ed.y]!=0) { continue; } //printf("%d %d %d\n",ed.x,ed.y,i); book[ed.x][ed.y]=i; pre_x[ed.x][ed.y]=st.x; pre_y[ed.x][ed.y]=st.y; Q.push(ed); } } return ; } int main() { scanf("%d %d %d",&a,&b,&c); bfs(); if(!flag) { printf("impossible\n"); } return 0; }