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

宽度优先搜索（BFS）

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

#define x first

#define y second

using namespace std;

typedef pair<int,int> 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<PII> 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<n;i++){

            for(int j=0;j<m;j++){

                cin>>g[i][j];

                if(g[i][j]=='S'){

                    start={i,j};

                }

            }

        }

        // cout<<start.x<<start.y<<endl;

        int distence=bfs(start);

        if(distence==-1){

            cout<<"oop!"<<endl;

        }else{

            cout<<distence<<endl;

        }

    }

    return 0;

}

巴特西

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

宽度优先搜索（BFS）

最新文章

热门文章