bfs的思想还是很好理解的，类似于树的层次遍历。
通过做两道题，看各种解题报告，终于大致知道代码是如何实现的了。（建议大家还是把数据结构相关的内容看完再写题，不然就会像我一样根基不稳 T T）
poj3984-迷宫问题
#include<cstdio> #include<cstring> #define Max 5 using namespace std; struct coord //坐标 { int cx; int cy; int pre;//记录前一个节点 }xy[33]; int map[Max][Max],vis[Max][Max];//map输入墙(1)与道路(0)，vis记录是否走过 int run[8]={1,0,0,1,-1,0,0,-1}; //右 下 左 上 int judge(int x,int y) //判断是否越界 { if(x>=1&&x<5&&y>=0&&y<5&&!map[x][y]) return 1; return 0; } void print(int tail) //基础的递归，个人感觉比堆栈好用哈 { int nod=xy[tail].pre; if(nod==-1) return ; print(nod); printf("(%d, %d) ",xy[nod].cx,xy[nod].cy); } void bfs() { int x,y; int head=0,tail=1; xy[head].cx=0;xy[head].cy=0;xy[head].pre=-1; while(head<tail) //从头遍历至尾，直至全部遍历结束或符合if条件跳出循环 { if(xy[head].cx==4&&xy[head].cy==4) //达到右下角时，跳出 { print(head); printf("(4, 4) "); return ; } for(int k=0;k<8;k+=2) //遍历头节点的所有子节点 { x=xy[head].cx+run[k]; y=xy[head].cy+run[k+1]; if(!vis[x][y]&&judge(x,y)) //未被走过且未越界 { vis[x][y]=1; xy[tail].cx=x; xy[tail].cy=y; xy[tail].pre=head; tail++; } } head++; //更新节点 }return; } int main() { for(int i=0;i<Max;i++) for(int k=0;k<Max;k++) scanf("%d",&map[i][k]); bfs(); return 0; }
本渣是根据这道题来学习广搜的，bfs()函数这段看了好几个小时才看明白（看懂后感觉当时的自己宛如智障T T）。
主要是不敢相信while(head<tail)这简单的一行竟然可以起到遍历全图的作用，又一次感受到了数据结构的魅力，嘻嘻。
poj3278-catch that cow
#include<cstdio> #include<cstring> #define Max 100001 using namespace std; int vis[Max]; struct far { int coord; //坐标 int pre; //记录前一个节点 }fj[Max]; void print(int head) { int flag=0; int nod=fj[head].pre; while(nod!=-1) { flag++; nod=fj[nod].pre; } printf("%d ",flag); } void bfs(int n,int k) { if(n==k) { printf("0 "); return ; } int head=0,tail=1; fj[head].coord=n; fj[head].pre=-1; vis[n]=1; while(head<tail) //依然是遍历 { long temp; if(fj[head].coord==k) { print(head); return; } for(int i=0;i<3;i++) //同上题 { if(i==0) temp=fj[head].coord+1; else if(i==1) temp=fj[head].coord-1; else temp=fj[head].coord*2; if(fj[head].coord<0||fj[head].coord>=Max) //剪枝 continue; if(!vis[temp]) { vis[temp]=1; fj[tail].coord=temp; fj[tail].pre=head; tail++; } } head++; } } int main() { int n,k; while(~(scanf("%d %d",&n,&k))) { memset(vis,false,sizeof(vis)); if(n>=k) printf("%d ",n-k); //剪枝 else bfs(n,k); } return 0; }
有了上一题的基础，这题做的还算顺手吧，刚开始自信满满敲完然后输入几个普通样例通过就交了。
结果： runtime error
于是去百度啥情况：
runtime error （运行时错误）程序运行到一半崩溃了。
例：①除以零
②数组越界
③指针越界
④使用已经释放的空间：int * p; p=(int *)malloc(5 * sizeof(int));free(p); *p=10;
⑤数组开得太大，超出了栈的范围，造成栈溢出
又回去专门看了那几个数组，调大后又迫不及待交了。
结果：runtime error
这才彻底确定是自己的思路不对，然后试了个样例：1 100000
结果： 程序运行失败
被一哥们嘲讽:
后来才知道是因为我追太猛了,跑过了.(即使他站着不动,但方向不对,又如何能寻着他呢?毕竟时间是有限的)
没错,这道题需要进行剪枝(优化时间)
然后又是一段修改,才终于过了.
/*
明天就要进行选拔了,昨天和负责教我的学长谈了很多.越来越感觉到,一个团队所能给我带来的,不仅仅是知识的学习,还有对生活,思想的指导.编程本身就是对人耐力与智力的考验与打磨.能够使人沉稳,理性.
我想,不管最后能不能留下来,我都不会放弃.
*/