C++ 深度优先搜索，DFS 讲解

目录

• DFS初步概念
• DFS例题-迷宫游戏
  • 题目描述
  • 输入输出格式
  • 输入输出样例
    • 输入#1
    • 输出#1
    • 输入#2
    • 输出#2
  • 解题思路
  • 代码

DFS初步概念

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

DFS例题-迷宫游戏

题目描述

这是一个迷宫游戏，有一个n×n的矩阵，矩阵内只能有#或.这两种字符，如果是#则是墙，如果是.则是可以走的路。起点是左上角，终点是右下角，每次只能往上、下、左、右四个方向走。

请你写一个程序，判断这个迷宫是否可以从起点走到终点。

输入输出格式

第1行一个整数n，代表矩阵大小为n×n。

第2~n+1行输入n×n的迷宫矩阵。

输出此迷宫是否能从起点走到终点，可以输出yes，不可以输出no。

输入输出样例

输入#1

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

输出#1

yes

输入#2

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

输出#2

no

解题思路

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

代码

#include <bits/stdc++.h>

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;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin >> 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;
}