C++ 深度优先搜索(DFS) 讲解

目录

• 1 DFS初步概念
• 2 DFS例题-迷宫游戏
  • 2.1 题目描述
  • 2.2 输入输出格式
  • 2.3 输入输出样例
    • 2.3.1 输入#1
    • 2.3.2 输出#1
    • 2.3.3 输入#2
    • 2.3.4 输出#2
  • 2.4 解题思路
  • 2.5 代码

1 DFS初步概念

DFS是一种深度搜索算法，它的特点是"不撞南墙不回头"，运用递归对不同方向的结果进行搜索。

2 DFS例题-迷宫游戏

2.1 题目描述

这是一个迷宫游戏，有一个$n\times n$的矩阵，矩阵内只能有#或.这两种字符，如果是#则是墙，如果是.则是可以走的路。起点是左上角，终点是右下角，每次只能往上、下、左、右四个方向走。
请你写一个程序，判断这个迷宫是否可以从起点走到终点。

2.2 输入输出格式

第$1$行一个整数$n$，代表矩阵大小为$n\times n$。
第$2$~$n+1$行输入$n\times n$的迷宫矩阵。
输出此迷宫是否能从起点走到终点，可以输出yes，不可以输出no。

2.3 输入输出样例

2.3.1 输入#1

5
..##.
#..##
..###
.####
.....

2.3.2 输出#1

yes

2.3.3 输入#2

5
..###
...##
..##.
##...
.##..

2.3.4 输出#2

no

2.4 解题思路

用char类型的二维数组maze存储输入的迷宫矩阵，用int类型的二维数组visited存储走过的地方，再用int类型的变量flag记录是否走完迷宫，flag初始值设为$0$，visited所有元素初始值设为$0$，maze与visited的下标是对应的，如果maze中的地方是#，则可以将visited相同下标元素的值设为$1$，再深度搜索可能的情况，若判断成功走到终点，则将flag设为$1$并结束递归。

2.5 代码

#include 

using namespace std;

char maze[105][105];
int visited[105][105],flag=0,n;
void dfs(int x,int y)//递归搜索函数
{
    if(x==n-1&&y==n-1)//走到终点的特判条件
    {
        flag = 1;
        return ;
    }
    else
    {
        if(!visited[x-1][y]&&x-1>=0)//上
        {
            visited[x-1][y] = 1;
            dfs(x-1,y);
        }
        if(!visited[x+1][y]&&x+1<=n-1)//下
        {
            visited[x+1][y] = 1;
            dfs(x+1,y);
        }
        if(!visited[x][y-1]&&y-1>=0)//左
        {
            visited[x][y-1] = 1;
            dfs(x,y-1);
        }
        if(!visited[x][y+1]&&y+1<=n-1)//右
        {
            visited[x][y+1] = 1;
            dfs(x,y+1);
        }
    }
}
int main()
{
    cin >> n;
    for(int i=0;ifor(int j=0;j> maze[i][j];
            if(maze[i][j]=='#')
            {
                visited[i][j] = 1;
            }
        }
    }
    if(visited[0][0]==1||visited[n-1][n-1]==1)
    {
        cout << "no" << endl;
        return 0;
    }
    dfs(0,0);
    if(flag==1) cout << "yes" << endl;
    else cout << "no" << endl;
    return 0;
}