题解 | 迷宫

#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
//两次bfs分别记录s和e可以到达的区域，再判断这些区域能不能使用一次激光连通.

int main() {
    int n,m;
    cin>>n>>m;
    vector<vector<char>> mg(n,vector<char>(m));
    int sx,sy,ex,ey;
    for(int i=0;i<n;i++){
        getchar();
        for(int j=0;j<m;j++){
            cin>>mg[i][j];
            if(mg[i][j]=='S'){sx=i;sy=j;}
            if(mg[i][j]=='E'){ex=i;ey=j;}
        }
    }
    vector<vector<char>> mg1(mg);
    vector<vector<int>> fx={{0,1},{1,0},{0,-1},{-1,0}};
    queue<pair<int,int>> que;
    set<int> si,sj,ei,ej;
    que.push({sx,sy});
    while(!que.empty()){
        auto [x,y]=que.front();
        que.pop();
        si.insert(x);
        sj.insert(y);
        if(mg[x][y]=='E'||abs(x-ex)<=1||abs(y-ey)<=1){cout<<"YES";return 0;}
        for(auto i:fx){
            int xx=x+i[0],yy=y+i[1];
            if(xx>=0&&xx<n&&yy>=0&&yy<m&&mg[xx][yy]!='#'){
              que.push({xx,yy});
              mg[xx][yy]='#';  
            }
        }
    }
    que.push({ex,ey});
    while(!que.empty()){
        auto [x,y]=que.front();
        ei.insert(x);
        ej.insert(y);
        que.pop();
        if(mg[x][y]=='S'||abs(x-sx)<=1||abs(y-sy)<=1){cout<<"YES";return 0;}
        for(auto i:fx){
            int xx=x+i[0],yy=y+i[1];
            if(xx>=0&&xx<n&&yy>=0&&yy<m&&mg[xx][yy]!='#'){
              que.push({xx,yy});
              mg[xx][yy]='#';  
            }
        }
    }
    for(int i:si){  
        if(ei.count(i)||ei.count(i+1)||ei.count(i-1)){cout<<"YES";return 0;}
    }
    for(int i:sj){
        if(ej.count(i)||ej.count(i+1)||ej.count(i-1)){cout<<"YES";return 0;}
    }
    cout<<"NO";
}