广度优先搜索入门

---

实现流程(用 queue )：

放入初始结点 S0 到 Open 表中(待访问)。如果 Open 表为空，失败退出。不为空，取出队头放入 Close 表(标记已经访问过)，即为节点 n。考察n是否为目标节点。是则成功退出。若不是，看 n 是否可扩展，不可扩展则退回第 2 步。若可扩展，则将其不再 Close 表和 Open (真正实现判重一般是为每个节点设置一个标记，而不是搜表)表中的子节点放入 Open 表的尾部，同时记录指向父节点的指针(可用于得到路径和层数)。转到第 2 步。

---

例题练习

题目1、POJ4001：抓住那头牛

描述 农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)。农夫有两种移动方式： 1、从X移动到X-1或X+1，每次移动花费一分钟 2、从X移动到2*X，每次移动花费一分钟

假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？

输入 两个整数，N和K

输出 一个整数，农夫抓到牛所要花费的最小分钟数

样例输入

5 17

样例输出

4

分析：

农夫和牛都位于一维的数轴，牛不动而农夫移动，最终目的是农夫移动到牛的位置。

这道题求最小分钟数，也就是最少步数，也就是最短路径的长度。

我们可以用深搜 + 剪枝来做，也可以用广搜来做。状态就是农夫所处的位置的下标 Xi ,那么初始状态是 N ，目标状态是 K ，状态转移是 Xi+1 、 Xi-1 或者 Xi*2。

AC代码

#include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; struct Node { int index; //当前节点的位置 int level; //当前节点所在层次 求路径就还要保留父节点位置 }; int N,K; //农夫和牛的初始位置 int visit[100010]; //标记数组，是否访问过 int minT; int main() { scanf("%d %d",&N,&K); memset(visit,0,sizeof(visit)); queue<struct Node> q; //初始节点入队 visit[N] == 1; Node node; node.index = N;node.level = 0; q.push(node); while(!q.empty()) { //取出队头 node = q.front();q.pop(); if(node.index == K) { printf("%d\n",node.level); //找到了，level就是层数，就是步数 return 0; } //能访问且未访问过 if(node.index - 1 >= 0 && visit[node.index - 1] == 0) { Node temp; temp.index = node.index - 1; temp.level = node.level + 1; q.push(temp); //放入队尾 visit[temp.index] = 1; } if(node.index + 1 <= 100000 && visit[node.index + 1] == 0) { Node temp; temp.index = node.index + 1; temp.level = node.level + 1; q.push(temp); //放入队尾 visit[temp.index] = 1; } if(node.index * 2 <= 100000 && visit[node.index * 2] == 0) { Node temp; temp.index = node.index * 2; temp.level = node.level + 1; q.push(temp); //放入队尾 visit[temp.index] = 1; } } return 0; }

---

例题练习

题目2、POJ4127:迷宫问题

描述 定义一个二维数组,它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, };

输入 一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

输出 左上角到右下角的最短路径，格式如样例所示。

样例输入

0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0

样例输出

(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4)

思路：

寻找最短路径，典型的广搜问题。因为深搜能找到最短路径长但是路径不好记录。

不能用queue了，因为queue模板中的出队就删除了节点，而我们需要保存节点来输出路径。

AC代码

#include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; struct Node { int r,c; //节点所在行列 int p; //节点的父亲的下标 }queue[10]; //自定义队列 int map[10][10]; int visit[10][10]; //标记数组 int head,tail; //队头下标，队尾下标 int dir[4][4] = {{1,0},{-1,0},{0,1},{0,-1}}; //方向数组 int main() { for(int i = 0; i < 5; i ++) for(int j = 0; j< 5; j ++) scanf("%d",&map[i][j]); memset(visit,0,sizeof(visit)); head=0;tail=0; //初始结点入队 Node node; node.r = 0;node.c = 0;node.p = -1; visit[0][0] = 1; queue[0] = node; tail++; while(head != tail) //head == tail 就表示队列为空 { Node node = queue[head]; //相当于front(); //达到终点 if(node.c == 4 && node.r == 4) { vector<struct Node> rode; //用vector保存路径的逆序 rode.push_back(node); int p = node.p; while(p != -1) { node = queue[p]; rode.push_back(node); p = node.p; } vector<struct Node >::iterator it; for(it = rode.end()-1; it >= rode.begin(); it --) { node = *it; cout<<"("<<(*it).r<<", "<<(*it).c<<")"<<endl; } return 0; } //不是终点 入队所有关联的点 for(int i = 0; i < 4; i++) { int tempR = node.r + dir[i][0]; int tempC = node.c + dir[i][1]; //能访问且未访问过 if(tempR >=0 && tempR <=4 && tempC >= 0 &&tempC <= 4) { if(visit[tempR][tempC] == 0 && map[tempR][tempC] == 0) { visit[tempR][tempC] = 1; Node tempN; tempN.r = tempR;tempN.c = tempC;tempN.p = head; queue[tail] = tempN; tail ++; } } } head ++; //相当于pop(); } return 0; }

拓展

POJ鸣人与佐助（广搜）