走出迷宫

链接：https://ac.nowcoder.com/acm/problem/14572

题目描述

小明现在在玩一个游戏，游戏来到了教学关卡，迷宫是一个N*M的矩阵。
小明的起点在地图中用“S”来表示，终点用“E”来表示，障碍物用“#”来表示，空地用“.”来表示。 障碍物不能通过。小明如果现在在点（x，y）处，那么下一步只能走到相邻的四个格子中的某一个：（x+1，y），（x-1，y），（x，y+1），（x，y-1）；
小明想要知道，现在他能否从起点走到终点。

输入描述：

本题包含多组数据。
每组数据先输入两个数字N,M接下来N行，每行M个字符，表示地图的状态。
数据范围：2<=N,M<=500保证有一个起点S，同时保证有一个终点E.

输出描述：

每组数据输出一行，如果小明能够从起点走到终点，那么输出Yes，否则输出No

solution：

模板题，因为不用求起点到终点的最小距离，因此可以不用再设一个数组来记录具体，把遍历过的点直接在图上改就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
char tu[505][505];
int n,m;
bool bfs(int sx,int sy)
{
    queue <P> q;
    tu[sx][sy]='#';
    q.push(P(sx,sy));
    while(!q.empty())
    {
        P p=q.front();q.pop();
        for(int i=0;i<4;i++)
        {
            int x=p.first+dx[i],y=p.second+dy[i];
            if(x<0||x>=n||y<0||y>=m)continue;
            if(tu[x][y]=='#')continue;
            if(tu[x][y]=='E')return true;
            tu[x][y]='#';
            q.push(P(x,y));
        }
    }
    return false;
}
int main()
{
    while(cin>>n>>m)
    {
        for(int i=0;i<n;i++)
            cin>>tu[i];
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(tu[i][j]=='S')
                {
                    if(bfs(i,j))
                        cout<<"Yes\n";
                    else
                        cout<<"No\n";
                }
            }
        }
    }
}