题目描述

小明现在在玩一个游戏，游戏来到了教学关卡，迷宫是一个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

题解

我之前DFS刚刚入门的时候做的就是这道题，这道题也算是一类经典DFS入门题吧~
DFS，深度优先搜索，就是只要我还能走，我就一条路走到头,直到我最后不能走的时候我再回头去找别的路。(我可怜的表达能力)

深度优先搜索所使用的策略就像其名字所隐含的：只要可能，就在图中尽量“深入”。深度优
先搜索总是对最近才发现的结点。的出发边进行探索，直到该结点的所有出发边都被发现为止。
二旦结点v的所有出发边都被发现，搜索则“回溯”到。的前驱结点（是经过该结点才被发现
的)，来搜索该前驱结点的出发边。该过程一直持续到从源结点可以达到的所有结点都被发现为
止。如果还存在尚未发现的结点，则深度优先搜索将从这些未被发现的结点中任选一个作为新
的源结点，并重复同样的搜索过程。该算法重复整个过程，直到图中的所有结点都被发现
为止。(摘自算法导论）

如果在初学DFS之前对于递归有着较好的理解，那么学起DFS来应该不是很困难。如果感觉在当下阶段无法透彻的理解DFS的话，也不要着急，可以去找一些蓝桥杯初赛的题来做一做，有很多关于DFS的妙用，尝试去理解代码并且可以自己独立的码出来，大概刷上几十道就可以对DFS有较好的理解了。我当时刚学的时候也一度理解不了后来刷了半个月的题才开始有点眉目。

对于本题，我们每一步都有四种方案去选择，对于从起点到终点的路径就是每一步不同方案之前组合起来的，究竟怎么样去选择，我们交给计算机去实现，利用DFS搜索所有路径，看是否有一条可以到达。

那我们要怎么写DFS程序呢？
我把DFS函数注上注释

int aa[4][2]={1,0,-1,0,0,1,0,-1};//方向数组
void dfs(int x,int y){
    if(x==xx&&y==yy)return ;//递归出口
    vis[x][y]=1;
    for(int i=0;i<4;i++){//枚举四种方案
        int fx=x+aa[i][0];
        int fy=y+aa[i][1];
        if(fx>=0&&fx<n&&fy>=0&&fy<m&&vis[fx][fy]==0&&a[fx][fy]!=&#39;#&#39;){
        //判断这个点是否可以走
            vis[fx][fy]=1;
            dfs(fx,fy);//可以走的话，继续走到下一步，即对此步进行DFS
        }
    }
}

完整代码

#include <bits/stdc++.h>
using namespace std;
const int N=550;
char a[N][N];
int vis[N][N];
int x,y,xx,yy;
int n,m;
int aa[4][2]={1,0,-1,0,0,1,0,-1};
void dfs(int x,int y){
    if(x==xx&&y==yy)return ;
    vis[x][y]=1;
    for(int i=0;i<4;i++){
        int fx=x+aa[i][0];
        int fy=y+aa[i][1];
        if(fx>=0&&fx<n&&fy>=0&&fy<m&&vis[fx][fy]==0&&a[fx][fy]!=&#39;#&#39;){
            vis[fx][fy]=1;
            dfs(fx,fy);
        }
    }
}
int main(){
    while(cin>>n>>m){
        getchar();
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>a[i][j];
                if(a[i][j]==&#39;S&#39;){
                    x=i;y=j;
                }
                if(a[i][j]==&#39;E&#39;){
                    xx=i;yy=j;
                }
            }
            getchar();
        }
        dfs(x,y);
        if(vis[xx][yy])cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}