学步园

这题的感触挺多的，第一次做bfs+记录路径的题目，貌似对bfs有点了解了

看了南开的一张ppt（讲搜索初步的），几个词总是在我脑海中徘徊：状态，状态转移，状态空间。

我们刚开始接触bfs都是从迷宫问题开始的，从而产生了思维定式，貌似觉得bfs就是和迷宫问题有关，不然我按什么策略去搜呢，其实不然。迷宫问题搜的方向，抽象出来，就是状态转移，只是迷宫问题的状态转移比较容易想到并且好写，而更广义的bfs则要我们去找出状态转移的策略。

状态空间则是bfs时所形成的搜索树

状态包括很多，当前的位置（这题中则是两个水壶的水），到这个状态所要的步数，还可以记录它的前一个状态，也可以记录这个状态是怎么得来的。

#include<iostream><br /> using namespace std;<br /> #include<cstdio><br /> struct State<br /> {<br /> int i,j,step,tr;<br /> State *pre;<br /> };<br /> State queue[1000];<br /> int visited[105][105];<br /> char e[7][10]={"","FILL(1)","FILL(2)","DROP(1)","DROP(2)"<br /> ,"POUR(1,2)","POUR(2,1)"};<br /> void bfs(int full_i,int full_j,int c)<br /> {<br /> int front=-1,rear=0;<br /> int result[1000];<br /> int t=0,h;<br /> State temp;<br /> State *p;<br /> bool flag=false;<br /> memset(visited,0,sizeof(visited));<br /> visited[0][0]=1;<br /> queue[0].i=0,queue[0].j=0,queue[0].step=0,queue[0].pre=NULL;<br /> while(front<rear)<br /> {<br /> p=&queue[++front];<br /> if(p->i==c||p->j==c)<br /> {<br /> flag=true;<br /> break;<br /> }<br /> if(p->i<full_i&&!visited[full_i][p->j])<br /> {<br /> visited[full_i][p->j]=1;<br /> temp.i=full_i;<br /> temp.j=p->j;<br /> temp.pre=p;<br /> temp.step=p->step+1;<br /> temp.tr=1;<br /> queue[++rear]=temp;<br /> }<br /> if(p->j<full_j&&!visited[p->i][full_j])<br /> {<br /> visited[p->i][full_j]=1;<br /> temp.i=p->i;<br /> temp.j=full_j;<br /> temp.pre=p;<br /> temp.step=p->step+1;<br /> temp.tr=2;<br /> queue[++rear]=temp;<br /> }<br /> if(p->i>0&&!visited[0][p->j])<br /> {<br /> visited[0][p->j]=1;<br /> temp.i=0;<br /> temp.j=p->j;<br /> temp.pre=p;<br /> temp.step=p->step+1;<br /> temp.tr=3;<br /> queue[++rear]=temp;<br /> }<br /> if(p->j>0&&!visited[p->i][0])<br /> {<br /> visited[p->i][0]=1;<br /> temp.i=p->i;<br /> temp.j=0;<br /> temp.pre=p;<br /> temp.step=p->step+1;<br /> temp.tr=4;<br /> queue[++rear]=temp;<br /> }<br /> if(full_j-p->j>p->i)<br /> if(!visited[0][p->i+p->j])<br /> {<br /> visited[0][p->i+p->j]=1;<br /> temp.i=0;<br /> temp.j=p->i+p->j;<br /> temp.pre=p;<br /> temp.step=p->step+1;<br /> temp.tr=5;<br /> queue[++rear]=temp;<br /> }<br /> if(full_j-p->j<p->i)<br /> if(!visited[p->i+p->j-full_j][full_j])<br /> {<br /> visited[p->i+p->j-full_j][full_j]=1;<br /> temp.i=p->i+p->j-full_j;<br /> temp.j=full_j;<br /> temp.pre=p;<br /> temp.step=p->step+1;<br /> temp.tr=5;<br /> queue[++rear]=temp;<br /> }<br /> if(full_i-p->i>p->j)<br /> if(!visited[p->i+p->j][0])<br /> {<br /> visited[p->i+p->j][0]=1;<br /> temp.i=p->i+p->j;<br /> temp.j=0;<br /> temp.pre=p;<br /> temp.step=p->step+1;<br /> temp.tr=6;<br /> queue[++rear]=temp;<br /> }<br /> if(full_i-p->i<p->j)<br /> if(!visited[full_i][p->i+p->j-full_i])<br /> {<br /> visited[full_i][p->i+p->j-full_i]=1;<br /> temp.i=full_i;<br /> temp.j=p->i+p->j-full_i;<br /> temp.pre=p;<br /> temp.step=p->step+1;<br /> temp.tr=6;<br /> queue[++rear]=temp;<br /> }<br /> }<br /> if(!flag)<br /> printf("impossible/n");<br /> else<br /> {<br /> printf("%d/n",p->step);<br /> while(p->pre)<br /> {<br /> result[t++]=p->tr;<br /> p=p->pre;<br /> }<br /> for(h=t-1;h>=0;h--)<br /> printf("%s/n",e[result[h]]);<br /> }<br /> }<br /> int main()<br /> {<br /> int a,b,c;<br /> while(scanf("%d%d%d",&a,&b,&c)!=EOF)<br /> bfs(a,b,c);<br /> return 0;<br /> }