本文共 3307 字，大约阅读时间需要 11 分钟。
(前面十几行是废话) zj昨天讲的(什么???) 如果n是13 (2/n, n-5 ,n-2)为例子 第0层 6 8 11 第1层 3 1 4 4 3 6 5 6 9 第2层 ....反正就是类似这样的, 如果下面又遇到了新的5啊这样的, 直接就continue了,因为它肯定不是最优的.... bfs 因为广度优先搜索，只会离初始点的步数一步步增多。 如果之后发现遇到了已走过的点，那肯定是从之前已走过的点那边走最短 而不是从之后发现的点走最短啊 POJ 3984典型的迷宫问题 典型的迷宫问题的话,我差不多明白了 row row row your boat https://cn.vjudge.net/problem/POJ-3984 有这么几个点 (.....所以zj昨天两个多小时都在讲什么???????) 1.因为是二位的,所以搞了个东西去记录x 和y的坐标 然后,他们是一一对应的,就是x和y的变化 point[4][2]={} 0 1 0 -1 -1 0 1 0 (写的时候写的是,0, -1 1 0 ...这样 2.进行搜索,那个rear,是类似 http://blog.csdn.net/raphealguo/article/details/7523411 里面写的队列,也就是染颜色... 用rear也是吧,如果你是需要等待被搜索的那个,就把你push进去那个队列,把队列一点点往外赶出去 判定条件可以是达到了最后那个条件就满足了 也可以是队列里面没元素了,就是所有的都访问过了 3.代码参考 http://blog.csdn.net/huanghanqian/article/details/51506732 这篇真写的不错 4.如果越界/被vist记录过,访问过,都需要continue掉 然后,如果它最先达到了,它一定是最短的 可以用反证法来说明,如果后面又遇到到达的,所花的步骤肯定比第一个到达的步骤要多 所以肯定是最短的 5.那么复杂度呢,(V+E) (不太懂)起码要有n,因为你最后到达了n 6.结构体里面的prev是记录了路径,上一个是啥 好了,现在我自己试着写一下这个POJ,稍后会公布抽出的核心代码(?) 这个版本的代码只是用front和rear模拟了一下队列.. //只有,把他们四个全都,遍历完成的时候,才算是出队 print(queue[rear - 1]);//为啥是rear-1? 大概.... 我感觉...因为是都遍历完成了,而且每一个节点,都只访问一次 每个节点都只访问一次,所以每个节点里面记录着的肯定都是最短的所以不怕吧 https://www.cnblogs.com/yueshuqiao/archive/2011/08/22/2149902.html 这个写的更清楚一点 第一个网址是帮助理解的吧,上2行这个网址写起来更通俗易懂一点 ****思维过程*****emmmm......输出问题卡了我一个小时,
前面.....我不想写了.....
#include(好吧,我承认这代码是错的.为什么错等下我会在评论区给.....orz) 按顺序来的,后面的front也就相当于前面的rear void print(Node now){ if(now.pre==-1) cout<<"("<<now.x<<", "<<now.y<<")"<<endl; else{ print(queue[now.pre]); cout<<"("<<now.x<<", "<<now.y<<")"<<endl; } } (趴) 8.print也可以这么写 9.忽然发现这个题有个特殊性...就是数组a这里,其实它完全已经帮助你优化好了..... vist为1 或者a输入的是1 都是走不到 初始化都是直接输入a当做初始化..... 我真的觉得很多身份堆到一起的时候脑子不够用.... fine,不管了,做好自己就好 关键是要对得起自己 其他的一切夸张点 全都是小事using namespace std;int a[5][5];int point[4][2] = { { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } };//x -1 0 1 0//y 0 -1 0 1//x和y,都有这么的几种选择//int vis[5][5] = { -1 };struct node { int x; int y; int pre;} b[50];//**作为一个结构体,它要有什么?//这个是一堆数组吧.. 然后d[i].x d[i.pre].x//int front = 0;int rear = 1;void print(int i) { //cout << "(" << d[i.pre].x << "," << d[i.pre].y <<")"<< endl; //要保证循环递归自己巴拉巴拉输出完了的话还是用递归来写 if (b[i].pre!=-1) { print(b[i].pre);//一直到等于-1,回到上一次的递归的下一行... cout << "(" << b[i].x << "," << b[i].y <<")"<< endl; } //i其实无关紧要,重要的是里面的x和y才是你想要的数值 /*//另一种写法 void print(node now) { if (now.prev != -1) { print(now.prev); cout<<... }//然后下面是传进来的node..一样吧应该 */ }void bfs(int x,int y) { int front = 0; b[front].x = 0; b[front].y = 0; b[front].pre = -1; while (front < rear)//队列里面,加入了的并且等待筛选的灰色地带还有的话,就 { //***先初始化 int newx, newy; //四个方向都走一遍吧 for (int i = 0; i <= 3; i++) { newx = b[front].x + point[i][0]; newy = b[front].x + point[i][1]; if (newx < 0 || newy < 0 ||newx>=5||newy>=5 ||a[newx][newy] == 1) continue; //else a[newx][newy] = 1; b[rear].x = newx; b[rear].y = newy; b[rear].pre = front; rear++;//入队...front还是当前作为那个啥,,,那个啥的啊 //rear当序号吧就...这个序号得更新过 //意会..哪个大哪个小其实都可以 //因为只是保存/只是提取你搜索的过程就可以了 if (newx == 1 && newy == 1) print(front); //***醒目***** //然而这里为什么又是front呢...因为front和rear就像是那篇很长的博文里面的点 //比如从v2出发可以到达v3 v4 v7 //v2相当于front v3 4 7相当于是rear //输出的时候(4,4)我们特判了,所以输出前驱 就可以啦. }front++; //四个方向都走完了的时候front也失去了意义,所以相当于出去了.. }}int main(){ for(int i=0;i<5;i++) for (int j = 0; j < 5; j++) { cin >> a[i][j]; } cout << "(0,0)" << endl; bfs(0, 0); cout << "(4,4)" << endl; return 0;}