【算法】（BFS/DFS）迷宫路径问题（C语言）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法】（BFS/DFS）迷宫路径问题（C语言）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 问题分析

题目：现有一迷宫如下图所示，蓝色部分为墙壁，白色部分为通路，入口在左上角（1,1）处，出口在右下角（8,8）处，试找出一条路径以通过该迷宫（路径不能重叠）。
【算法】（BFS/DFS）迷宫路径问题（C语言）

分析：
① 使用二维数组来存储迷宫，墙用 1 表示，路用 0 表示，如下图所示：
【算法】（BFS/DFS）迷宫路径问题（C语言）为与题目中的入口坐标 (1,1) 和出口坐标 (8,8) 对应，二维数组第 0 行和第 0 列不存储迷宫，用 1 填充。

② 对于任意一点（x,y），下一步都有前后左右四个可能的方向，即（x+1,y）,（x-1,y）,（x,y+1）,（x,y-1），使用 fx[4] = { -1,1,0,0 }和 fy[4] = { 0,0,-1,1 } 来模拟下一步走向。

③ 搜索方式可以选择广度优先搜索（BFS） 或 深度优先搜索（DFS）。广度优先搜索利用了队列的先进先出性质，找到的路径是一条最短的通路；深度优先搜索利用了递归回溯的思想，所找到的路径不一定是一条最短通路。

2. 基于BFS搜索一条路径

使用数组来模拟队列操作实现广度优先搜索，设置队头队尾指示器qh和qe，通过这两个变量的增减来模拟入队和出队操作。

搜索过程如下图所示：
【算法】（BFS/DFS）迷宫路径问题（C语言）
若其中某一步时队列为空（即qh==qe），说明该迷宫没有通路。

2.1 完整代码及注释文章来源地址https://www.toymoban.com/news/detail-471793.html

# include<stdio.h>
# define N 9

int maze[N][N] = {
   {
   1,1,1,1,1,1,1,1,1},		//迷宫，1表示墙，0表示路，入口为maze[1][1]，出口为maze[8][8]
				 {
   1,0,0,0,0,0,0,0,0},		//maze[0][0]至maze[0][8]和maze[0][0]至maze[8][0](即第一行和第一列)不在迷宫范围内，用1填充。
				 {
   1,0,1,1,1,1,0,1,0},
				 {
   1,0,0,0,1,1,0,1,0},
				 {
   1,0,1,0,0,0,0,1,0},
				 {
   1,0,1,0,1,1,0,1,0},
				 {
   1,0,1,0,0,0,0,1,1},
				 {
   1,0,1,0,0,1,0,0,0},
				 {
   1,0,1,1,1,1,1,1,0}};
int fx[4] = {
    -1,1,0,0 }, fy[4] = {
    0,0,-1,1 };		//每个点的上下左右四个方向扩展

struct {
   			//存放路径坐标和前一个坐标的位置
	int x, y, pre;
}sq[100];

int Check(int i, int j);			//检查当前坐标是否可行
void Output(int qe);				//输出路径坐标

/*模拟队列操作实现广度优先搜索*/
void Path_Search() {
   
	int i, j, k, qh = 0, qe = 1;
	maze[1][1] = -1;				//置-1表示当前坐标已走过
	sq[1].pre = 0;
	sq[1