bfs 学习笔记

?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).\n",Ans);
   }
  
}

bfs 学习笔记

原文：https://www.cnblogs.com/KingBenQi/p/12305899.html