當(dāng)你從一個頂點(diǎn)開始，沿著某條路往下走，一直走到底，如果走完后發(fā)現(xiàn)不能達(dá)到目標(biāo)解，就回溯，返回到上一個節(jié)點(diǎn)，換條路，然后繼續(xù)走到底，如此往復(fù)，直至所有可能的結(jié)果都被搜索完。通俗理解就是不撞南墻不回頭這種感覺，這個就是我們這篇要講解的內(nèi)容，下面帶領(lǐng)大家結(jié)合實(shí)例系統(tǒng)的學(xué)習(xí)一下。

一、什么是DFS？

DFS簡單講叫深度優(yōu)先搜索，就是指：優(yōu)先考慮深度，換句話說就是一條路走到黑，直到無路可走的情況下，才會選擇回頭，然后重新選擇一條路。

二、DFS的實(shí)現(xiàn)

原理：DFS是由棧的形式實(shí)現(xiàn)的，通過棧進(jìn)行路徑儲存。

DFS的實(shí)現(xiàn)步驟：

（1）從頂點(diǎn)出發(fā)。

（2）訪問頂點(diǎn)，也就是根節(jié)點(diǎn)。

（3）依次從頂點(diǎn)的未被訪問的鄰接點(diǎn)出發(fā)，進(jìn)行深度優(yōu)先遍歷；直至和頂點(diǎn)有路徑相通的頂點(diǎn)都被訪問。

（4）若此時尚有頂點(diǎn)未被訪問，則從一個未被訪問的頂點(diǎn)出發(fā)，重新進(jìn)行深度優(yōu)遍歷，直到所有頂點(diǎn)均被訪問過為止。

三、DFS的注意事項(xiàng)

（1）剪枝 剪枝是為了減少時間成本

（2）回溯 回溯回到原來路徑

（3）還原 回到原來路徑時，要還原現(xiàn)場

四、基礎(chǔ)案例

題目描述：馬在中國象棋以日字形規(guī)則移動。

請編寫一段程序，給定 n?m 大小的棋盤，以及馬的初始位置 (x，y)，要求不能重復(fù)經(jīng)過棋盤上的同一個點(diǎn)，計(jì)算馬可以有多少途徑遍歷棋盤上的所有點(diǎn)。

輸入格式：第一行為整數(shù) T，表示測試數(shù)據(jù)組數(shù)。

每一組測試數(shù)據(jù)包含一行，為四個整數(shù)，分別為棋盤的大小以及初始位置坐標(biāo) n,m,x,y。

輸出格式：每組測試數(shù)據(jù)包含一行，為一個整數(shù)，表示馬能遍歷棋盤的途徑總數(shù)，若無法遍歷棋盤上的所有點(diǎn)則輸出 0。

數(shù)據(jù)范圍：

1≤T≤9,

1≤m,n≤9,

0≤x≤n?1,

0≤y≤m?1

輸入樣例：

1

5 4 0 0

輸出樣例：

32

題解(DFS)分析：馬只能走“日”字形，那么移動一次只能有八種情況出現(xiàn)，如圖所示。

很顯然，是DFS模型的變形，把可以到達(dá)的鄰接點(diǎn)距離寫成數(shù)組，再分析題目，由于要尋找多條道路，故每次尋路完畢需要進(jìn)行回溯。貼上代碼。

#include <iostream>
#define xa x + a[i]
#define yb y + b[i]
using namespace std;

int m, n, x, y, cnt = 0;
const int a[]={1,2,2,1,-1,-2,-2,-1};
const int b[]={2,1,-1,-2,-2,-1,1,2};
bool g[10][10];

void dfs(int x, int y, int dc){
    if(dc == 0){
        cnt ++;
        return;
    }
    g[x][y] = true;
    for(int i = 0; i < 8; i++){
        if(xa >= 0 && xa < m && yb >= 0 && yb < n && !g[xa][yb]) 
            dfs(xa, yb, dc - 1);
    }
    g[x][y] = false;
}

int main(){
    int t = 0; 
    cin >> t;
    while(t--){
        cin >> m >> n >> x >> y;
        dfs(x, y, n * m - 1);
        cout << cnt << endl;
        cnt = 0;
    }
    return 0;
}