關于DFS(深度優先搜索）

關于DFS（深度優先搜索）

一年前開始接觸c語言 后來學了演算法 因為沒堅持下來就放棄了一段時間，現在想重新撿起來，就算不為了拿下什么獎，也為了自己以后能說起來我也堅持過學一些東西，

因為本來就是個小白，而且csdn上關于dfs的講解也有很多，所以接下來的理解僅供記錄自己學習，如有錯誤歡迎指正，

先說說為什么寫dfs吧，最近打了場比賽，dfs題很多，突然就想到搜索演算法在比賽中很常用，學會用的話很多題都很好寫，所以今天又去學了一下，

下面先把題掛一下：

這是一道簡單的：

其實就是一個簡單的迷宮，入口是S,出口是E，#為不能走的路，輸出的最短時間就是最短路，直接掛代碼，

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
int min = 9999999;
int c[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };	//上下左右四個方向
int m,n,r,t,q,w; //m,n為行，列 r,t為終點坐標，q,w為起點坐標
char s[1000][1000];		
void dfs(int x, int y, int step)			
{
    int i, xn, yn;
    if (x == r && y == t)	//到終點			
    {							
        if (step < min)		//否則不存在路徑	
            min = step;
        return;
    }
    for (i = 0; i < 4; i++)		
    {
        xn = x + c[i][0];			//移動
        yn = y + c[i][1];	
        if (xn < 0 || xn >= m || yn < 0 || yn >= n)	 //出界情況
        {
            continue;			
        }
        if (s[xn][yn] == 0)		//0為可以走	
        {
            s[xn][yn] = 1;		//標記走過		
            dfs(xn, yn, step + 1);	//到新位置繼續搜索下一個位置		
            s[xn][yn] = 0;	//置為零方便回溯時繼續搜索		
        }
    }
    return;
}
int main()
{
    int i, j;
    scanf("%d %d",&m, &n);
    getchar();
    for (i = 0; i < m; i++)
    {
        for (j = 0; j < n; j++)
        {
            s[i][j] = getchar();
        }
        getchar();
    }
    for (i = 0; i < m; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (s[i][j] == 'S') {
                s[i][j] = 0;
                int q = i; //記錄起點
                int w = j;
            }
            else if (s[i][j] == '.'){  //可走為零
                s[i][j] = 0;

            }
            else if (s[i][j] == '#') //不可走的置為1
            {
                s[i][j] = 1;
            }
            else if (s[i][j] == 'E') { //記錄終點
                r = i;
                t = j;
                s[i][j] = 0;
            }


        }
    }
    dfs(q, w, 0); //從起點開始搜索
    printf("%d", min);	//最短路徑				
}

這里我是把符號都置為0和1，將地圖改變了一下，

相信大家都看得懂，下面開始寫我對DFS的理解：
1.深度優先搜索，顧名思義，深度，我的理解就是一條路走到底，當深到不能再深了，我再退回來換條路深，直到沒路可以換即走完了所有情況，所以也叫暴力搜索，

2.DFS的關鍵應該就是記錄自己走過的路和沒走過的路，所以要用0和1去標記，否則你走不通要回溯的時候不知道要回哪去，

3.因為是窮舉所有情況，所以有時時間復雜度較高，至于如何改變，就涉及到dfs的剪枝，這里先了解一下這個詞，具體我會在下面解釋，

下面掛一個我在我喜歡的博主那里拿來的樹，觀察一下DFS究竟是怎么以深度搜索的：

然后這個搜索的順序就是
a->b->e->b->f->c->f->b->c->b->a->c->a->d->g->d->a
你可能會問，為什么我b->f->c已經到過了c，回溯到b后還要再去c呢，其實很容易想明白，如果c是終點，那最短路當然不是a->b->f->c，當然是a->c，那這是怎么做到的呢，這一點我在上面代碼上也有掛出，回溯后置為零的操作，這樣的話避免了因此錯過更優解法，還有一個問題，那我到達c之后，為什么不走a呢，顯而易見，那不就成環了嗎，你現在還處于走過a的狀態，a值為1，所以不能走，這樣也避免了無限回圈搜索的結果，這里提一句最優化剪枝，如果我已經得到了a->c這條長度為2的路，那在之后所有路徑只要大于二，也就是說如果我走了兩步還沒到終點，我就不走了，我就要回到第一步再找其他的路了，這樣就省下了很多無用的搜索，

然后再掛一個不一樣的DFS：

很容易理解就是用最少的炸彈數炸掉3X3方格中所有的’E’，每個炸彈可以炸上下左右以及中間五個格，炸彈放的位置是隨意的，所以我們可以把每一個位置放不放炸彈的所有情況全部列出來，即有2的九次方為512種情況，用DFS的話可以很快算出，下面看代碼：

#include <stdio.h>
int min(int a, int b) { return a < b ? a : b; } //三目運算子寫函式
const int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
//上下左右
int atack[5][5]; //記錄每個位置被炸彈波及次數
char MP[5][5]; //地圖
int ans = 1e9;

void dfs(int x, int y, int bomb) { //bomb為炸彈數
    if (x == 4) { //x最大為3，為4時遍歷完畢
        bool ok = true;
        for (int i = 1; i <= 3; i++)
            for (int j = 1; j <= 3; j++)
                if (MP[i][j] == 'E' && !atack[i][j]) ok = false; 
                //判斷'E'處是否被炸彈波及
        if (ok) ans = min(ans, bomb);
        return;
    }
    ++atack[x][y]; //投放炸彈的情況
    for (int i = 0; i < 4; i++) {
        int nx = x + dir[i][0], ny = y + dir[i][1];
        ++atack[nx][ny]; //上下左右記錄
    }
    if (y == 3) dfs(x + 1, 1, bomb + 1); //換下一行，使用炸彈，炸彈數加1
    else dfs(x, y + 1, bomb + 1); //換下一列

    --atack[x][y]; //不投放炸彈的情況
    for (int i = 0; i < 4; i++) {
        int nx = x + dir[i][0], ny = y + dir[i][1];
        --atack[nx][ny];
    }
    if (y == 3) dfs(x + 1, 1, bomb); //不投放炸彈，炸彈數不變
    else dfs(x, y + 1, bomb);
}

int main() {
    for (int i = 1; i <= 3; i++) scanf("%s\n", &MP[i][1]);
    dfs(1, 1, 0); //從（1，1）處遍歷
    printf("%d\n", ans); //最小炸彈數
    return 0;
}

比上一題稍難一點，仔細看dfs的使用情況也不難理解，也就是記錄下每一個位置投炸彈與不投炸彈的所有情況，再進行比較選出最少炸彈數的情況輸出，

剪枝：剪枝就是通過一些判斷，剪掉一些不必要的子樹，因為這個分枝上都不是我們想要的結果，就沒必要再去搜索它了，比如，在走迷宮時，如果發現當前的步數已經超過了最優步數，那從這個狀態開始的搜索全都多余了，就可以省去大量的搜索，還有一些重復性剪枝之類的都與此類似，就不在這里多說了，

以后再有有趣的題我還是會掛上來的，可以繼續關注，