广度优先(BFS)

先看一道简单的题，迷宫问题：

洛谷P1746 离开中山路：P1746 离开中山路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<iostream>
#include<cstring>
#include<queue>
#include <utility>
#define N 1002
using namespace std;


char g[N][N];
int dist[N][N];
queue< pair<int,int> > q;
int n,x1,y1,x2,y2;

int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};

void bfs(int x,int y)
{
	q.push(make_pair(x,y));
	dist[x][y]=0;
	while(!q.empty())
	{
		pair<int,int> t = q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			int a = t.first + dx[i];
			int b = t.second + dy[i];
			
			if(a<1 || a>n || b<1 || b>n) continue;
			if(g[a][b] != '0') continue;
			if(dist[a][b] >=0) continue;
			
			q.push(make_pair(a,b));
			dist[a][b] = dist[t.first][t.second] +1;
			
			if(a==x2 && b==y2) return ;
		}
		
	}
	
}

int main()
{
	memset(dist,-1,sizeof(dist));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",g[i] +1);
	}
	scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
	bfs(x1,y1);
	printf("%d",dist[x2][y2]);
	
	return 0;
}

先看一下遍历顺序：

可以看出BFS和DFS有着很大的区别，并不是“一条路，走到黑”。而是根据举例根节点的具体进行遍历。

假如先确定顺序是从左到右，那么有什么办法可以从左到右进行遍历呢？

很难想？那就别想了，直接上答案：队列。先进先出啊。

是不是很神奇？