DFS可以(至少现在我发现)解决2种(细分3种问题)：迷宫和连通块

迷宫

其主要思想是for循环寻找起点，DFS搜索，上下左右四个位置。如果其中一个位置还有路可走，就dfs(x,y),如果4个位置都无路可走，就回溯到上一层，当然我们还要定义一个数组记录该点是否走过(如果回溯，还需将此位置重新设置成未走过.)

注意:我的程序并不会输出迷宫的最优解(最短路径)！！

C++ 代码

/*输入说明：先输入迷宫的行和列，然后输入迷宫：S代表起点，T代表终点，点(.)代表路，星号(*)代表墙(障碍物)
如果有路则输出Yes，否则输出No.
*/ 
#include <bits/stdc++.h>
using namespace std;
int n,m;
string __map[110];
int flag[110][110]= {0};
bool in(int x,int y)
{
    if(x>=0&&x<n&&y>=0&&y<m)
    {
        return true;
    }
    else
    {
        return false;
    }
}
bool dfs(int x,int y)
{
    if(__map[x][y]=='T')
    {
        return true;
    }
    flag[x][y]=1;
    __map[x][y]='m';
    int tx=x-1,ty=y;
    if(in(tx,ty)&&__map[tx][ty]!='*'&&flag[tx][ty]==0)
    {
        if(dfs(tx,ty))
        {
            return true;
        }
    }
    tx=x,ty=y-1;
    if(in(tx,ty)&&__map[tx][ty]!='*'&&flag[tx][ty]==0)
    {
        if(dfs(tx,ty))
        {
            return true;
        }
    }
    tx=x+1,ty=y;
    if(in(tx,ty)&&__map[tx][ty]!='*'&&flag[tx][ty]==0)
    {
        if(dfs(tx,ty))
        {
            return true;
        }
    }
    tx=x,ty=y+1;
    if(in(tx,ty)&&__map[tx][ty]!='*'&&flag[tx][ty]==0)
    {
        if(dfs(tx,ty))
        {
            return true;
        }
    }
    flag[x][y]=0;
    __map[x][y]='.';
    return false;
}
int main()
{
    int x,y;
    cin>>n>>m;
    for(int i=0; i<n; i++)
    {
        cin>>__map[i];
    }
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(__map[i][j]=='S')
            {
                x=i,y=j;
            }
        }
    }
    if(dfs(x,y))
    {
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }
    for(int i=0; i<n; i++)
    {
        cout<<__map[i]<<endl;

    }
    return 0;
}

但你会发现：它在处理特别复杂的迷宫时会tle，怎么办呢？
注意下列代码：

int tx=x-1,ty=y;
    if(in(tx,ty)&&__map[tx][ty]!='*'&&flag[tx][ty]==0)
    {
        if(dfs(tx,ty))
        {
            return true;
        }
    }
    tx=x,ty=y-1;
    if(in(tx,ty)&&__map[tx][ty]!='*'&&flag[tx][ty]==0)
    {
        if(dfs(tx,ty))
        {
            return true;
        }
    }
    tx=x+1,ty=y;
    if(in(tx,ty)&&__map[tx][ty]!='*'&&flag[tx][ty]==0)
    {
        if(dfs(tx,ty))
        {
            return true;
        }
    }
    tx=x,ty=y+1;
    if(in(tx,ty)&&__map[tx][ty]!='*'&&flag[tx][ty]==0)
    {
        if(dfs(tx,ty))
        {
            return true;
        }
    }

其实，这4段代码都在干”搜路”这种相同的事情，只不过方向不同。
于是乎我们定义一个表示方向的数组

int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

那么刚刚烦人的4段就变成了：

for(int i=0;i<4;i++){
        int tx=x+dir[i][0];
        int ty=y+dir[i][1];
        if(in(tx,ty)&&!vis[tx][ty]&&maze[tx][ty]!='*'){
            if(dfs(tx,ty)){
                return true;
            }
        }
    }

我们只需修改一下程序即可：

#include <iostream>
#include <string>
using namespace std;
int n, m;
string maze[110];
int sx, sy;
bool vis[110][110];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
bool in(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}
bool dfs(int x, int y) {
    vis[x][y]=true;
    if(maze[x][y]=='T'){
        return true;
    }
    for(int i=0;i<4;i++){
        int tx=x+dir[i][0];
        int ty=y+dir[i][1];
        if(in(tx,ty)&&!vis[tx][ty]&&maze[tx][ty]!='*'){
            if(dfs(tx,ty)){
                return true;
            }
        }
    }
    return false;
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> maze[i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(maze[i][j]=='S'){
                sx=i;
                sy=j;
            }
        }
    }
    if (dfs(sx, sy)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

(还是)迷宫，(但是)现在要求计算一共有多少种走法。

有了上一次的基础，这一次就简单了，只需在到终点再次回溯即可：

#include<bits/stdc++.h>
using namespace std;
int maze[10][10];//迷宫
bool visit[10][10];//访问数组，1--访问过
int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};//方向数组
int zong;//总数
int qx, qy, zx, zy;//起点、终点
int t, n, m; 
void dfs(int x, int y){
//坐标
    if(x==zx && y==zy){
        zong++;//方案数加1
        return; 
    }
    visit[x][y] = 1;//标记已经访问过了
    for(int i=0; i<=3; i++){//四个方向 
        int dx = x + dir[i][0];
        int dy = y + dir[i][1];
        if(visit[dx][dy]==0 && maze[dx][dy]==1){
            //没有走过、没有障碍物 
            dfs(dx, dy);//深搜一步  
        } 
    }
    visit[x][y]=0;//回溯一步(还原现场) 
    return;//返回上一层 
}
int main(){
    int i, j;
    cin>>n>>m>>t;//行、列  障碍个数
    for(i=1; i<=n; i++){
        for(j=1; j<=m; j++){
            maze[i][j]=1;//地图全部置1 
        }
    } 
    cin>>qx>>qy>>zx>>zy;//起点、终点
    for(i=1; i<=t; i++){
        int tmpx, tmpy;
        cin>>tmpx>>tmpy;//障碍物
        maze[tmpx][tmpy]=0; 
    } 
    dfs(qx, qy);//深搜
    cout<<zong<<endl;//输出总数 
    return 0;
} 

连通块问题

我通常采用”涂色”算法，就是用dsf不断作死输入，让整个区域都变成空格，每做一次，ans++。

例题

暑假到了，生活在“河西走廊”上的小榔每天都要出去放羊。放羊的时候，小榔发现羊会自行分群吃草。所以，小榔想知道每天放羊的时候会分为多少群。

小榔家的草场是一个面积N×M（1<=N,M<=100）N×M（1<=N,M<=100）的草场，其中，用’.’表示草，用‘#’表示羊。一只羊附近（上、下、左、右四个方向）的羊归属于同一群。

输入
第一行，一个正整数T，表示组数（天数）；（T（1<=T<=100）T（1<=T<=100））

每组数据包含两个信息——第一行，草场的长和宽（N×M（1<=N,M<=100）N×M（1<=N,M<=100））；接下来N×MN×M表示草场的信息。

输出
对于每组信息，输出该组中羊群的数量。

#include <bits/stdc++.h>
using namespace std;
int __map[110][110]= {0};
int m,n,T,ans;
char ch;
int direction[4][2]= {{-1,0},{1,0},{0,1},{0,-1}};
bool in(int x,int y)
{
    if(x>=0&&x<n&&y>=0&&y<m)
    {
        return true;
    }
    else
    {
        return false;
    }
}
void dfs(int x,int y)
{
    __map[x][y]=0;
    int tx,ty;
    for(int i=0; i<4; i++)
    {
        tx=x+direction[i][0];
        ty=y+direction[i][1];
        if(in(tx,ty)&&__map[tx][ty]==1)
        {
            dfs(tx,ty);
        }
    }
    return ;
}
int main()
{
    cin>>T;
    for(int i=1; i<=T; i++)
    {
        memset(__map,0,sizeof(__map));
        ans=0;
        cin>>n>>m;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                cin>>ch;
                if(ch=='#')
                {
                    __map[i][j]=1;
                }
                else if(ch=='.')
                {
                    __map[i][j]=0;
                }
            }
        }
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(__map[i][j]==1)
                {
                    ans++;
                    dfs(i,j);
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

最后我想吐槽一点：NOIP 2020有一道DFS的程序阅读题，结果我计算太”好”, 一个又没算出来，真是太™伤心了！