????????????
????????????Hello，大家好我是[上进小菜猪]，一个有趣的全栈博主，欢迎关注，多多关照????????????
????????????欢迎大家找我合作学习（文末有VX与公众号 想进学习交流群or学习资料or一起刷题 欢迎++）????????????
????????????苟怀四方志，所在可游盘，一起加油进步！????????????
????????????

一，拯救甘雨

标签：IMUSTACM 第二届校赛 大题

时间限制：1Sec内存限制：128MB

题目描述
甘雨孤身一人前往古迹寻找阿莫斯之弓，可却迷失在迷宫中。迷宫是一个 N * M 的矩阵，甘雨的位置通过字符“S”进行标识，迷宫的出口通过字符“E”进行标识，字符“.”表示可以行走的道路，字符“#”表示无法通过的墙壁。时间紧迫，甘雨能否顺利走出迷宫？
注意：甘雨每次行动只能够前往上下左右相邻的四个区域。

输入
输入包含多组测试数据，每组数据表示如下：
第一行包含两个正整数 N（2 ≤ N ≤ 500）和 M（2 ≤ M ≤ 500），表示地图的尺寸；
接下来的 N 行，每行包含 M 个字符，表示迷宫的状态。数据保证迷宫内只有一个起点和一个终点。

输出
每组数据对应一行输出，如果甘雨可以从走出迷宫，则输出“Yes”，否则输出“No”（均不含引号）。
样例输入

3 3
S..
..E
...
3 3
S##
###
##E

样例输出

Yes
No

DFS连通：c++

#include<bits/stdc++.h>
using namespace std;
int n,m;
int book[1005][1005];
char a[1005][1005];
bool in(int x,int y)
{
    return 0<=x&&x<n&&0<=y&&y<m;
}
bool dfs(int i,int j)
{
    if(a[i][j]=='E'){
        return true;
    }
    book[i][j]=1;
    int tx=i-1,ty=j;
    if(in(tx,ty)&&a[tx][ty]!='#'&&!book[tx][ty])
    {
        if(dfs(tx,ty))
        {
            return true;
        }
    }
    tx=i,ty=j-1;
    if(in(tx,ty)&&a[tx][ty]!='#'&&!book[tx][ty])
    {
        if(dfs(tx,ty))
        {
            return true;
        }
    }
    tx=i+1,ty=j;
    if(in(tx,ty)&&a[tx][ty]!='#'&&!book[tx][ty])
    {
        if(dfs(tx,ty))
        {
            return true;
        }
    }
    tx=i,ty=j+1;
    if(in(tx,ty)&&a[tx][ty]!='#'&&!book[tx][ty])
    {
        if(dfs(tx,ty))
        {
            return true;
        }
    }
    return false;

}
int main()
{
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>a[i][j];
        }
    }
    int x,y;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(a[i][j]=='S')
            {
                x=i,y=j;
            }

        }
    }


    for(int i=0;i<1000;i++)
    {
        for(int j=0;j<1000;j++)
        {
            book[i][j]=0;
        }
    }
    if(dfs(x,y))
    {
        cout<<"Yes"<<endl;
    }
    else
    {

        cout<<"No"<<endl;
    }


    }


return 0;
}

ps：非常经典的DFS问题

二，END

????????????关注作者，持续阅读作者的文章，一起学习更多知识！
[点击关注，联系作者，进入群聊，一起刷题]????????????

如果有更优解法及其思路，欢迎讨论。