前置课程：

第37课结构体、第41课队列

BFS 全称是 [Breadth First Search],中文名是宽度优先搜索，也叫广度优先搜索。

是图上最基础、最重要的搜索算法之一。

所谓宽度优先。就是每次都尝试访问同一层的节点。 如果同一层都访问完了，再访问下一层。

这样做的结果是，BFS 算法找到的路径是从起点开始的 最短 合法路径。换言之，这条路径所包含的边数最小。

在 BFS 结束时，每个节点都是通过从起点到该点的最短路径访问的。

1.故事起源 有一只蚂蚁出去寻找食物，无意中进入了一个迷宫。蚂蚁只能向上、下、左、右4个方向走，迷宫中有墙和水的地方都无法通行。这时蚂蚁犯难了，怎样才能找出到食物的最短路径呢？

2.思考 蚂蚁在起点时，有4个选择，可以向上、下、左、右某一个方向走1步。

如果蚂蚁走过了一段距离，此时也依然只有4个选择。 当然要排除之前走过的地方（不走回头路，走了也只会更长）和无法通过的墙和水。

蚂蚁想，还好我会影分身。如果每一步都分身成4个蚂蚁，向4个方向各走1步，这样最先找到食物的肯定就是最短的路径了（因为每一步都把能走的地方都走完了，肯定找不出更短的路径了）。

而且还能看出，第1步会到达所有到起点距离为1的地方，第2步也会到达所有距离为2的地方。 如此类推，第n步会覆盖所有到起点最短距离为n的地方。

3.问题建模 把迷宫地图放在二维数组中，能通行的地方为0，墙和水的地方为负数。

每一步向4个方向走，可以通过当前坐标(x,y)加上一个方向向量。

这个其实就是宽度优先搜索(BFS)的思想。

4.宽度优先搜索(BFS) 又称广度优先搜索，优先向四周扩展子节点，是最简便的图的搜索算法之一，一般通过队列来实现。

int n,m;//一般输入的行列数/边界
struct node{
	int x, y, s;
};//保存点的信息 

int dx[]={};//x方向 
int dy[]={};//y方向 
int vis[n][m],mapp[N][N];//vis初始化应该在主函数

int BFS(int x,int y)
{
	//起点特判，也可以在主函数中特判 
    if(x == endx && y == endy)//满足条件
    {     
        return 1;
    }
    
    queue<node> q;
    q.push({x, y, 1});//将起始点先放进队列 
    vis[x][y] = 1;//标记起始点
	while(!q.empty())//队列非空表示有路径可搜 
	{
		int tx = q.front().x;
		int ty = q.front().y;
		int ts = q.front().s;//取出队首的点
		q.pop();//将队首抛弃 
		for()
		{
			int xx = tx + dx[];
			int yy = ty + dy[]; 
			if(xx == endx && yy == endy)//满足条件 
			{
				return ts + 1;
			} 
			//判断是否在边界内，是否不可搜索，是否曾搜索过
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy])
			{
				vis[xx][yy] = 1;
				q.push({xx, yy, ts + 1});//将新的可搜点放进队列 
			}
		} 
	}   
    return -1;//如果搜不到 
}