无锡网站营销推广,中国黄金集团建设有限公司官方网站,禁止指定ip访问网站,郑州网站提升排名结合队列的知识利用 广度优先遍历#xff0c;通过对能走的路径的记录以及对走过路径的标记#xff0c;进行多条路搜查
一、理论基础
如下图的迷宫#xff1a; 选取所走方向#xff08;针对某一个位置#xff09;下#xff0c;右#xff0c;上#xff0c;左#xff0… 结合队列的知识利用 广度优先遍历通过对能走的路径的记录以及对走过路径的标记进行多条路搜查
一、理论基础
如下图的迷宫 选取所走方向针对某一个位置下右上左从起点0,0开始进行广度搜索标记0,1走过重复寻路直到走到终点
如图 通过一个点找到所有与该顶点相连且能走的顶点不停寻找直到找到目的地或走完所有能走的点为止图中可以看到 任意一个顶点只有一个前驱可以通过某种方式记录该顶点的前驱一步步回到原点并记录移动轨迹最终得到从起点到终点最短路径的数组
步骤
1起点入队
2队头出队
3找到所有与队头相连且为空地的点将这些点都入队并记录这些点的前驱
4重复执行步骤23直到队列为空
5通过终点一步步回到前驱最终回到终点得到最短路径\
二、代码实现
C语言代码实现如下
① 定义坐标结构体
typedef struct
{int row; //行int col; //列
}Position;
② 定义队列结构及操作
typedef struct
{Position*queue; //队列int front; //头部int rear; //尾部int cap; //队列容量
}MyQueue;//判断队列是否已满
bool IsEmpty(MyQueue*myqueue)
{if(myqueue-frontmyqueue-rear)return true;elsereturn false;
}
//弹出队头
Position PopFront(MyQueue*myqueue)
{Position pmyqueue-queue[myqueue-front];myqueue-front(myqueue-front1)%myqueue-cap;return p;
}
//插入队尾
void PushRear(MyQueue*myqueue,Postion p)
{myqueue-queue[myqueue-rear]p;myqueue-rear(myqueue-rear1)%myqueue-cap;
}
③ 设置移动方向 //移动方向
int orient[4][2]{{1,0},{0,1},{-1,0},{0,-1}//下 右 上 左
}
④ 开始广度寻路
//0代表空地1代表墙
void ShortestPath_BFS(int**maze,int maze_row,int maze_col,Position start,Position destination)
{//创建队列MyQueue*myqueueCreatMyQueue(maze_row*maze*col);/*创建vt数组标记某些点是否走过0代表未走过非0代表走过1代表该点的前驱在该点下方2代表该点的前驱在该点右边3代表上4代表左*/int vt[maze_row][maze_col];memset(vt,0,sizeof(vt)); //对所有点初始化标记为未走过PushRear(myqueue,start); //起点入队vt[start.row][start.col]5; //标记起点已走过5代表起点位置while(!IsEmpty(myqueue)){Position tempPopFront(myqueue); //队头出队//找到与出队顶点相连且为空地的所有顶点入队for(int ori0;ori4;ori){//定义试探点int newRowtemp.roworient[i][0];int newColtemp.colorient[i][1];//判断试探点是否能走if(newRow0newRowmaze_rownewCol0newColmaze_colmaze[newRow][newCol]0vt[newRow][newCol]0)//不越界且为空地未走过{//该点入队Position p;p.rownewRow;p.colnewCol;PushRear(queue,p);//标记该点走过,记录该点前驱方向vt[newRow][newCol](ori2)%41;}}}//定义路径数组Position*pathmalloc(sizeof(Position)*maze_row*maze_col);int path_size0;//通过终点回到前驱直到回到起点记录其移动轨迹int curRowdestination.row;int curColdestination.col;while(vt[curRow][curCol]!5){path[path_size].rowcurRow;path[path_size].colcurCol;path_size;int orivt[curRow][curCol]-1;//前驱点相对于该点的方向在orient数组中的位置curRoworient[ori][0]; //前驱点的行curColorient[ori][1]; //前驱点的列}//将起点位置存入路径数组path[path_size].rowstart.row;path[path_size].colstart.col;path_size;//展示从起点开始到终点的路径for(int ipath_size-1;i0;i--){printf((%d,%d)path[i].row,path[i].col);if(i!0)printf(-);}
}
