题解 | #走出迷宫#

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespaces std;
const int N=510;
int x1,y1,x2,y2;//记录起点和终点
int n,m;
char maze[N][N];//迷宫
bool st[N][N];//判断是否走过
queue<int> q;//用一维来进行，pos=x*m+y，二维与一维的转换
int dir[4][2]={-1,0,0,1,1,0,0,-1};
void bfs()
{
	int pos=x1*m+y1;
    q.push(pos);
    st[x1][y1]=false;
    while(!q.empty())
    {
        pos=q.front();
        q.pop();
        int x=pos/m,y=pos%m;
        if(x==x2&&y==y2)
        {
            cout<<"Yes"<<endl;
            return ;
        }
        for(int i=0; i<4; i++)
        {
            int dx=x+dir[i][0];
            int dy=y+dir[i][1];
            if(!st[dx][dy]&&dx>=0&&dy>=0&&dx<n&&dy<m&&(maze[dx][dy]=='.'||maze[dx][dy]=='E'))
            {
                q.push(dx*m+dy);
                st[dx][dy]=true;
            }
        }
    }
    cout<<"No"<<endl;
    return ;
}
int main()
{
    while(cin>>n>>m)
    {
        while(!q.empty())q.pop();//要注意更新
        memset(st,false,sizeof st);//要注意更新
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                cin>>maze[i][j];
                if(maze[i][j]=='S')x1=i,y1=j;
                if(maze[i][j]=='E')x2=i,y2=j;
            }
        }
        bfs();
    }
    return 0;
}