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;
}