用栈模拟深度优先搜索

题目原型来自HDUOJ的1372 Knight Moves
很简单的一个搜索题
就是告诉你棋盘上的两个点,然后让你算出Knight,也就是国际象棋的马,最少多少步能够从一个点到另一个点。
算法很简单,深搜即可,这个不是本文讨论的问题。这里我是把原来通过函数递归调用的深搜改为用栈自行模拟
代码如下:

#include #include 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; }; stackzerob; int main() { char str1[3],str2[3]; node head,p; while(scanf("%s %s",str1,str2)2) { for(int i=0;ihead.t||ans-1) ans=head.t; continue; } for(int i=0;i=0 && p.x=0 && p.y后记:
其实当你理解了深搜和广搜后,你会发现,你写出来的深搜和广搜的代码可以看上去是差不多的。为什么那么说呢,因为,无论那种搜索,都是通过对一个线性表进行处理,只不过是先处理头部还是尾部的问题罢了。处理头部优先的时候,就是广度优先了,因为,头部的都是兄弟节点;而尾部的则是深度优先,因为放入尾部的都是刚刚生产出来的节点——也就是所谓一条路走到死。
同理可以联想到启发式搜索。启发式搜索就是先以你自定义的优先级处理,然后再以广度为优先级处理。
所以,归根结底,所谓的搜索,就是一种定义了优先级的枚举。当然,这个只是我个人的理解,欢迎各位大牛拍转。