迷宫相关算法文章：
《算法笔记》—— “迷宫求解” 之 深度优先搜索（DFS）

BFS 用到了队列的知识，什么是队列，这里我就不说了 . . .
BFS 与 DFS 不一样的是，BFS 是针对于层面上的，一层一层的通过队列来筛选 . . .

我们还是以 BFS中的迷宫为例来讲解 BFS的使用.
BFS 求解迷宫是将当前点的所有可能性放入队列之中（入队），然后再去掉队列的头部（出队）…

例如下图所示：

BFS 思想解析：

首先我们将 （0，0）点加入队列，此时该点是队列的头，然后我们将该点四个方向所有的点都加入队列之中，出了迷宫的点、障碍物或者是已经加入队列的点不算，之后把队头去掉，以下一个新的队头继续开始遍历，直至找到终点为止 . . .

队列图所示：

首先将起点作为队头，然后将四个方向的点入队

队头出队，队头的下一个元素作为队头

下面我来一步一步讲解 BFS的使用方式.

1. 与 BFS中需要相同的数据

// 地图 
 int map[5][5] = {
	  0 ,0 ,0 ,1 ,1 ,
	  0 ,0 ,0 ,1 ,1 , 
	  0 ,1 ,0 ,0 ,0 ,
	  0 ,0 ,0 ,1 ,1 ,
	  0 ,0 ,0 ,0 ,0
};

int flag[5][5] = { 0 };  // 标记是否走过的路

// 方向 
int direction[4][2] = {
	  0, 1,
	  1, 0,
	  0, -1,
	  -1, 0
};

2. 声明队列的元素类型

struct note  // 队列中的元素类型 
{
    int x;   // 行下标
    int y;   // 列一标
};

3. 定义队列，并初始化队头的元素

struct note que[25];
int head = 0;    // 队列的头部索引 
int tail = 0;    // 队列的尾部索引 

// 初始化每一个队列元素的值（开始寻找的地方）
que[head].x = que[head].y = 0;   
tail++;  	 // 尾部索引 + 1
flag[0][0] = 1;  // 标记初始位置已经查找过了

4. 核心部分，开始 BFS

while(head < tail)  // 队列永远都有数据
{
    int i = 0;
    for(; i < 4; i++)	// 该点的四个方向
    {
       	// 每次都是以队头为单位向四个方向开始
       	int nx = que[head].x + direction[i][0];   
   	int ny = que[head].y + direction[i][1];
   	
   	// 判断该点的坐标是否满足要求
   	if(nx < 0 || nx > 4 || ny < 0 || ny > 4)
    		continue;
   	
   	if(map[nx][ny] == 0 && flag[nx][ny] == 0)
   	{
    		flag[nx][ny] = 1; 
    		que[tail].x = nx;     // 加入队列 
    		que[tail].y = ny;
    		tail++;    
   	}
   	
   	if(nx == 4 && ny == 4)	      // 判断是否找到终止了
   	{
    		printf("Yes, I found it !");
    		return 0;
   	}
    }
  
    head++;		// 队头已经失去意义了，开始下一点的循环

}

BFS核心的思想就是队列的使用，层级原理，和二叉树的层级遍历一个方式 . . .
此处可以看看我一篇文章：红黑树基本功能 —— C++实现

.

下面来展示完整的 BFS源码：

#include <stdio.h>
struct note  // 队列中的元素类型 
{
	int x;
 	int y; 
}; 

int main()
{
 	// 地图 
 	int map[5][5] = {
		  0 ,0 ,0 ,1 ,1 ,
		  0 ,0 ,0 ,1 ,1 , 
		  0 ,1 ,0 ,0 ,0 ,
		  0 ,0 ,0 ,1 ,1 ,
		  0 ,0 ,0 ,0 ,0
	};
	
	int flag[5][5] = { 0 };  // 标记是否走过的路
 	
 	// 方向 
 	int direction[4][2] = {
		  0, 1,
		  1, 0,
		  0, -1,
		  -1, 0
	}; 
	
	struct note que[25];	// 队列
 	
 	int head = 0;   // 队列的头部索引 
 	int tail = 0;   // 队列的尾部索引 
 	
 	// 初始化每一个队列元素的值（开始寻找的地方）
 	que[head].x = que[head].y = 0;   
 	tail++;  // 尾部索引 + 1
 	flag[0][0] = 1;  // 标记初始位置已经查找过了
 
 	while(head < tail) 
 	{
  		int i = 0;
  		for(; i < 4; i++)
  		{
   			// 每次都是以队头为单位向四个方向开始
   			int nx = que[head].x + direction[i][0];   
 			int ny = que[head].y + direction[i][1];
   			
   			if(nx < 0 || nx > 4 || ny < 0 || ny > 4)
    				continue;
   			
   			if(map[nx][ny] == 0 && flag[nx][ny] == 0)
   			{
    				flag[nx][ny] = 1; 
    				que[tail].x = nx;     // 加入队列 
    				que[tail].y = ny;
    				tail++;    
   			}
   			
   			if(nx == 4 && ny == 4)
   			{
    				printf("Yes, I found it !");
    				return 0;
   			}
  		}
  		
  		head++;
 	}
 	
 	return 0;
}

运行程序结果如下图所示：

当我们把终点周围的点都换成障碍物时，结果如下：

好了，你们快去试试吧，BFS 和 DFS可以求解出很多的问题，比如人工智能贪吃蛇、连连看等等 . . .

.

作者：浪子花梦