BFS是一种借用队列来存储的过程，分层查找，优先考虑距离出发点近的点。无论是在邻接表还是邻接矩阵中存储，都需要借助一个辅助队列，v个顶点均需入队，最坏的情况下，空间复杂O（v）。
邻接表形式存储时，每个顶点均需搜索一次，时间复杂度T1=O（v），从一个顶点开始搜索时，开始搜索，访问未被访问过的节点。最坏的情况下，每个顶点至少访问一次，每条边至少访问1次，这是因为在搜索的过程中，若某结点向下搜索时，其子结点都访问过了，这时候就会回退，故时间复 杂度为O(E)，算法总的时间复 度为O(|V|+|E|)。
邻接矩阵存储方式时，查找每个顶点的邻接点所需时间为O(V)，即该节点所在的该行该列。又有n个顶点，故算总的时间复杂度为O(|V|^2)。
模版题 POJ 2251 三维BFS
https://vjudge.net/contest/65959#problem/B
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int L,R,C,step;
char tmp[33][33][33];
bool map[33][33][33],vis[33][33][33];
struct Point{
int l,r,c,step;
}S,E,now,Next;
int dl[]={-1,1,0,0,0,0};
int dr[]={0,0,0,0,-1,1};
int dc[]={0,0,-1,1,0,0};
int bfs(){
queue<Point>Q;
step=0;
Q.push(S);
vis[S.l][S.r][S.c]=1;
while(!Q.empty()){
now=Q.front();
Q.pop();
if(now.l==E.l&&now.r==E.r&&now.c==E.c)return now.step;
for(int i=0;i<6;i++){
Next.l=now.l+dl[i],Next.r=now.r+dr[i],Next.c=now.c+dc[i],Next.step=now.step+1;
if(!map[Next.l][Next.r][Next.c]&&!vis[Next.l][Next.r][Next.c]){
Q.push(Next);
vis[Next.l][Next.r][Next.c]=1;
}
}
}
return -1;
}
int main(){
while(scanf("%d%d%d",&L,&R,&C)&&L!=0){
memset(tmp,0,sizeof(tmp));
memset(map,1,sizeof(map));
memset(vis,0,sizeof(vis));
for(int i=1;i<=L;i++)
for(int j=1;j<=R;j++)
for(int k=1;k<=C;k++)
cin>>tmp[i][j][k];
for(int i=1;i<=L;i++)
for(int j=1;j<=R;j++)
for(int k=1;k<=C;k++){
map[i][j][k]=(tmp[i][j][k]=='#');
if(tmp[i][j][k]=='S') S.l=i,S.r=j,S.c=k,S.step=0;
if(tmp[i][j][k]=='E') E.l=i,E.r=j,E.c=k;
}
int Ans=bfs();
if(Ans==-1)cout<<"Trapped!"<<endl;
else printf("Escaped in %d minute(s).
",Ans);
}
}
模版题 POJ 3278 Catch the cow
https://vjudge.net/problem/POJ-3278
这个的边界判断真的鬼屎，一定要判断边界，要不然会runtime error！
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxk 100000
int n,k;
struct Object{
int x,step;
}Now,Next;
bool vis[100005];
queue<Object> Q;
int main(){
scanf("%d%d",&n,&k);
if(n>k){
cout<<abs(n-k)<<endl;
return 0;
}
Now.step=0;
Now.x=n;
vis[n]=1;
Q.push(Now);
while(!Q.empty()){
Now=Q.front();Q.pop();
if(Now.x==k){
cout<<Now.step<<endl;
return 0;
}
if(Now.x+1>=0&&Now.x+1<=maxk&&!vis[Now.x+1]){
Next.x=Now.x+1;
vis[Next.x]=1;
Next.step=Now.step+1;
Q.push(Next);
}
if(Now.x-1>=0&&Now.x-1<=maxk&&!vis[Now.x-1]){
Next.x=Now.x-1;
vis[Next.x]=1;
Next.step=Now.step+1;
Q.push(Next);
}
if(Now.x*2>=0&&Now.x*2<=maxk&&!vis[Now.x*2]){
Next.x=Now.x*2;
vis[Next.x]=1;
Next.step=Now.step+1;
Q.push(Next);
}
}
}