深度度优先搜索DFS骑士跳跃问题.doc

《深度度优先搜索DFS骑士跳跃问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、深度度优先搜索DFS骑士跳跃问题#include#includeusingnamespacestd;#defineINF99999intmap[8][8];intdir[8][2]={{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}};structnode{intx,y,t;};stackzerob;intmain(){charstr1[3],str2[3];nodehead,p;while(scanf

2、("%s%s",str1,str2)==2){for(inti=0;i<8;i++){for(intj=0;j<8;j++){map[i][j]=INF;}}while(!zerob.empty()){zerob.pop();}head.x=str1[0]-'a';head.y=str1[1]-'1';head.t=0;intans=-1;zerob.push(head);while(!zerob.empty()){head=zerob.top();zerob.pop();if(head.x==str2[0

3、]-'a'&&head.y==str2[1]-'1'){if(ans>head.t

4、

5、ans==-1)ans=head.t;continue;}for(inti=0;i<8;i++){p=head;p.x+=dir[i][0];p.y+=dir[i][1];if(!(p.x>=0&&p.x<8&&p.y>=0&&p.y<8))continue;p.t++;if(map[p.x][p.y]<=p.t)continue;map[p.x][p.y]=p.t;zerob.push(p);}}printf("Toge

6、tfrom%sto%stakes%dknightmoves.",str1,str2,ans);}}其实当你理解了深搜和广搜后，你会发现，你写出来的深搜和广搜的代码可以看上去是差不多的。为什么那么说呢，因为，无论那种搜索，都是通过对一个线性表进行处理，只不过是先处理头部还是尾部的问题罢了。处理头部优先的时候，就是广度优先了，因为，头部的都是兄弟节点；而尾部的则是深度优先，因为放入尾部的都是刚刚生产出来的节点——也就是所谓一条路走到死。