题目原型来自HDUOJ的1372 Knight Moves
很简单的一个搜索题
就是告诉你棋盘上的两个点，然后让你算出Knight，也就是国际象棋的马，最少多少步能够从一个点到另一个点。
算法很简单，深搜即可，这个不是本文讨论的问题。这里我是把原来通过函数递归调用的深搜改为用栈自行模拟
代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | #include<stdio.h> #include<stack> using namespace std; #define INF 99999 int map[8][8]; int dir[8][2]={{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}}; struct node{ int x,y,t; }; stack<node>zerob; int main() { char str1[3],str2[3]; node head,p; while(scanf("%s %s",str1,str2)==2) { for(int i=0;i<8;i++) { for(int j=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; int ans=-1; zerob.push(head); while(!zerob.empty()){ head=zerob.top(); zerob.pop(); if(head.x==str2[0]-'a'&&head.y==str2[1]-'1') { if(ans>head.t||ans==-1) ans=head.t; continue; } for(int i=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("To get from %s to %s takes %d knight moves.\n",str1,str2,ans); } } |
后记：
其实当你理解了深搜和广搜后，你会发现，你写出来的深搜和广搜的代码可以看上去是差不多的。为什么那么说呢，因为，无论那种搜索，都是通过对一个线性表进行处理，只不过是先处理头部还是尾部的问题罢了。处理头部优先的时候，就是广度优先了，因为，头部的都是兄弟节点；而尾部的则是深度优先，因为放入尾部的都是刚刚生产出来的节点——也就是所谓一条路走到死。
同理可以联想到启发式搜索。启发式搜索就是先以你自定义的优先级处理，然后再以广度为优先级处理。
所以，归根结底，所谓的搜索，就是一种定义了优先级的枚举。当然，这个只是我个人的理解，欢迎各位大牛拍转。
评论:2
参与评论