题目描述

广度优先搜索bfs;  模板题

算法1

C++ 代码

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define x first
#define y second
const int INF=0x3f3f3f;
typedef pair<int,int> PII;
const int N=210;
int n,m;
char g[N][N];
int dist[N][N];
bool st[N][N];

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

void bfs(PII start,PII end){
    memset(st,false,sizeof(st));
    memset(dist,INF,sizeof(dist));
    queue<PII> q;
    st[start.x][start.y]=true;
    dist[start.x][start.y]=0;
    q.push(start);
    while(q.size()){
        PII t=q.front();q.pop();
        //扩展
        int a=t.first,b=t.second;
        for(int i=0;i<4;i++){
            int nx=a+dx[i];
            int ny=b+dy[i];
            if(nx<1||nx>n||ny<1||ny>m||st[nx][ny]||g[nx][ny]=='#'){continue;}
            if(dist[nx][ny]>dist[a][b]+1){
                dist[nx][ny]=dist[a][b]+1;
                st[nx][ny]=true;
                q.push({nx,ny});
            }
        }
    }
}

int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        PII start,end;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>g[i][j];  
                if(g[i][j]=='S'){
                    start={i,j};    
                }
                if(g[i][j]=='E'){
                    end={i,j};
                }
            }
        }

        bfs(start,end);
        if(dist[end.x][end.y]>INF){
            cout<<"oop!"<<endl;
        }else{
            cout<<dist[end.x][end.y]<<endl;
        }
    }

    return 0;
}