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類型的變量pass記錄是否走完迷宮，pass初始值設為\(0\)，visited所有元素初始值設為\(0\)，maze與visited的下標是對應的，如果maze中的地方是#，則可以將visited相同下標元素的值設為\(1\)，再深度搜索可能的情況，若判斷成功走到終點，則將pass設為\(1\)并結束遞歸。

2.5 代碼

#include <bits/stdc++.h>
#include <windows.h>

using namespace std;

int n,visited[105][105]={},dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},pass=0;//迷宮大小，標記數組，方向數組，是否通過
char maze[105][105]={};//迷宮數組
void dfs(int x,int y) {
    if(x==n-1&&y==n-1) {//到達終點
        pass = 1;
        return ;
    }
    for(int i=0;i<4;i++) {
        int nx=x+dx[i],ny=y+dy[i];
        if(nx>=0&&nx<=n-1&&ny>=0&&ny<=n-1&&visited[nx][ny]==0) {
            visited[nx][ny] = 1;
            dfs(nx,ny);//符合條件，開始遞歸
        }
    }
}
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;
        system("pause");
        return 0;
    }
    dfs(0,0);//執行函數
    if(pass==1) {//通過
        cout << "Yes" << endl;
    }
    else {//未通過
        cout << "No" << endl;
    }
    system("pause");
    return 0;
}