广度优先搜索（C++代码实现）

2024-07-04 00:02| 来源: 网络整理| 查看: 265

广度优先搜索（C++代码实现）

题目问题，请参照我的上一篇文章（深度优先搜索）。

思考一下，上次的深度优先搜索是从起点开始顺时针的顺序进行方向选择下一个路径点；那么这次的广度优先搜索，顾名思义，就是这个点可以移动到的下一步位置的所有点都进行测试，再以这些点为路径的头点，进行下一个点的搜索…

代码如下（含注释）

#include using namespace std; struct note { int x;//X坐标 int y;//Y坐标 int s;//步数 }; int main() { //定义队列，路径，50*50，最多不超过2500 struct note que[2501]; //a用来记录地图，0可以行走，1表示有障碍；book用来记录走过的路径点，防止走重复的路径 int a[51][51] = { 0 }, book[51][51] = { 0 }; //定义一个游走方向的数组，方便方向的改变 int next[4][2] = { {0,1},//向右 {1,0},//向下 {0,-1},//向左 {-1,0}//向上 }; //定义查找的路径上的头尾 int head, tail; //startX,startY为路径起点坐标；p,q为目的地坐标；tx,ty为走的过程中的坐标；flag用来标记是否到达目的地 int i, j, k, n, m, startX, startY, p, q, tx, ty, flag; cin >> n >> m; for (i = 1; i cin >> a[i][j]; } } cin >> startX >> startY >> p >> q; //初始化队列 head = 1; tail = 1; //往队列插入迷宫入口的坐标 que[tail].x = startX; que[tail].y = startY; que[tail].s = 0; tail++; book[startX][startY] = 1; flag = 0; //队列不为空的时候循环 while (head //计算下一个点的坐标 tx = que[head].x + next[k][0]; ty = que[head].y + next[k][1]; //判断是否越界 if (txm) { continue; } //判断障碍物和路径是否走过 if (a[tx][ty] == 0 && book[tx][ty] == 0) { //此点可以走，那么久标记此点走过 book[tx][ty] = 1; //插入tx,ty这个新点到队列中 que[tail].x = tx; que[tail].y = ty; que[tail].s = que[head].s + 1; tail++; } //如果到目的地，停止扩展，任务结束，退出循环 if (tx == p && ty == q) { flag = 1; break; } } if (flag == 1) { break; } //当一个点扩展结束后，head++继续对后面的点扩展 head++; } cout

【本文地址】

公司简介

联系我们