算法基础⑦搜索与图论--BFS（宽度优先搜索）

宽度优先搜索（BFS）

#include
#include
#include
#include
#include
#define x first
#define y second
using namespace std;
typedef pair PII;
const int N=210;
char g[N][N];
int dis[N][N];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int n,m;
int T;
int bfs(PII start){
    queue q;
    memset(dis,-1,sizeof dis);
    dis[start.x][start.y]=0;
    q.push(start);
    while(!q.empty()){
        PII t=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int a=t.x+dx[i],b=t.y+dy[i];
            if(a>=n||a<0||b>=m||b<0)continue;
            if(g[a][b]=='#')continue;
            if(dis[a][b]!=-1)continue;
            
            if(g[a][b]=='E')return dis[t.x][t.y]+1;
            
            q.push({a,b});
            dis[a][b]=dis[t.x][t.y]+1;
        }
    }
    return -1;
}
int main(){
    cin>>T;
    while(T--){
        cin>>n>>m;
        PII start;
        for(int i=0;i>g[i][j];
                if(g[i][j]=='S'){
                    start={i,j};
                }
            }
        }
        // cout<