上一章我们编写了一个小游戏：炸弹人游戏。使用广度优先搜索解决的，本章将用深度优先搜索来解决。

《关于广度优先搜索解决炸弹人游戏和炸弹人游戏的描述》点击查看

《什么是深度优先搜索》点击查看    

深度优先搜索的核心代码如下：说白了，就是一条路走到黑，然后回头倒着走看看有没有别的岔路口，不断递归。

void dfs(int x, int y){

    int next[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    int k, sum, tx, ty;

    sum = getnum(x, y);

    if(sum > max){

        max = sum;

        mx = x;

        my = y;

    }

    for(k=0; k<4; k++){

        tx = x + next[k][0];

        ty = y + next[k][1];

        //判断边界

        if(tx<0 || tx > n-1 || ty < 0 || ty > n-1) continue;

        //判断墙和是否走过

        if(a[tx][ty] != '.' || book[tx][ty] != 0) continue;

        book[tx][ty] = 1;

        dfs(tx, ty);

    }

    return;

}

深度优先搜索实现炸弹人游戏的完整代码如下：

#include<stdio.h>

char a[20][20];

int book[20][20], max, mx, my, n, m;

//获取点（i, j）可以炸死多少敌人。

int getnum(int i, int j);

//深度优先搜索，对点(x, y)进行深度优先搜索

void dfs(int x, int y);

void main(){

    int i, startx, starty;

    //地图长n，宽m，起始位置坐标为startx，starty

    scanf("%d %d %d %d", &n, &m, &startx, &starty);

    for(i=0; i<n; i++){

        printf("Line : %d", i);

        scanf("%s", a[i]);

    }

    book[startx][starty] = 1;

    max = getnum(startx, starty);

    mx = startx;

    my = starty;

    dfs(startx, starty);

    printf("炸弹放在%d,%d的位置，可以炸死%d人", mx, my, max);

}

int getnum(int i, int j){

    int x, y, sum=0;

    //统计点(i, j)的左边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        x--;

    }

    //统计点(i, j)的右边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        x++;

    }

    //统计点(i, j)的上边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        y--;

    }

    //统计点(i, j)的下边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        y++;

    }

    return sum;

}

void dfs(int x, int y){

    int next[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    int k, sum, tx, ty;

    sum = getnum(x, y);

    if(sum > max){

        max = sum;

        mx = x;

        my = y;

    }

    for(k=0; k<4; k++){

        tx = x + next[k][0];

        ty = y + next[k][1];

        //判断边界

        if(tx<0 || tx > n-1 || ty < 0 || ty > n-1) continue;

        //判断墙和是否走过

        if(a[tx][ty] != '.' || book[tx][ty] != 0) continue;

        book[tx][ty] = 1;

        dfs(tx, ty);

    }

    return;

}

输入：第一次要求输入地图的长、宽、起始X坐标、起始Y坐标：13 13 3 3

第二次要求输入的就是地图了，每次一行，如下：

#############

#GG.GGG#GGG.#

###.#G#G#G#G#

#.......#..G#

#G#.###.#G#G#

#GG.GGG.#.GG#

#G#.#G#.#.#.#

##G...G.....#

#G#.#G###.#G#

#...G#GGG.GG#

#G#.#G#G#.#G#

#GG.GGG#G.GG#

#############

输出：炸弹放在7，11的位置，可以炸死10人.

Ps:代码案例来源于《啊哈！算法》一书

    什么是广度优先搜索？广度优先搜索也称为宽度优先搜索，一层一层不断的扩展来达到搜索的目的。以一个点为中心，将上下左右4个点都搜索过后，再以这4个点分别为中心点，搜索该中心点的上下左右4个点，依次类推。

    场景：比如我们要从点(1,1)到点（5，5），我们使用广度优先算法来找出最短路劲。

    第一步：将点(1,1)的上下左右4个点找出，走过的点忽略，不能走的点忽略（比如水，墙），那么只有（1，2）和（2，1）2个点，因为（1，0）和（0，1）已经超出了地图范围。

    第二步：将第一步得出的点(1,2)的上下左右4个点找出，走过的点忽略，不能走的点忽略，那么只有（1，3）和（2，2）2个点，因为（0，2）已经超出了地图范围，（1,1)已经走过了。

    第三步：将第一步得出的将点(2,1)的上下左右4个点找出，走过的点忽略，不能走的点忽略，那么只有（3，1）这一个点，因为（2，0）已经超出了地图范围，（1,1)已经走过了。（2，2）在第二部已经得出了。

    ……

    依次类推，将每个点都尝试过后，则比较每种方式的长度，得出最短路径。

    代码将展示另一个实例。我们都玩过炸弹人的游戏，地图中有墙和敌人，在地图的空地上方一个炸弹，炸弹会在上下左右4个直线方向炸出4道火花，敌人会被炸死，而墙不会受到影响。基于此，我们用广度优先算法来实现哪个点可以炸死的敌人数量最多。

    1、建立一个队列，将起点（人物刚出的时候在地图的位置）作为队列的第一个元素。按照队列的顺序来执行。

    2、将这个点的上下左右4个点也依次入队。然后把起点出队。

    3、这时把队列的第一个元素（起点的右边的点）作为中心点，将这个点的上下左右4个点依次入队，然后这个点出队。            4、这时把队列的第一个元素（起点的下边的点）作为中心点，将这个点的上下左右4个点依次入队，然后这个点出队。            5、这时把队列的第一个元素（起点的左边的点）作为中心点，将这个点的上下左右4个点依次入队，然后这个点出队。            6、这时把队列的第一个元素（起点的上边的点）作为中心点，将这个点的上下左右4个点依次入队，然后这个点出队。            7、这时把队列的第一个元素（起点的右边的点的右边的点）作为中心点，将这个点的上下左右4个点依次入队，然后这个点出队。

    ……

    依次类推，总之，就是把一个点作为中心点，然后把这个点的上下左右依次入队，按照队列顺序，队列中每个点都要作为中心点，把中心点上下左右4个点依次入队。直到队列没有元素时停止。

    我们约定，敌人为“G”，墙为“#”，空地为“.”。

    计算一个点可以炸死的敌人数量的函数getnum()如下：

int getnum(int i, int j){

    int x, y, sum=0;

    //统计点(i, j)的左边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        x--;

    }

    //统计点(i, j)的右边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        x++;

    }

    //统计点(i, j)的上边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        y--;

    }

    //统计点(i, j)的下边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        y++;

    }

    return sum;

}

    入队操作的代码如下：

//起点入队

    que[tail].x = startx;

    que[tail].y = starty;

    tail++;

    book[startx][starty] = 1;

    max = getnum(startx, starty);

    mx = startx;

    my = starty;

    广度优先搜索的核心代码如下：

//广度优先搜索的核心部分

    while(head < tail){

        for(k = 0; k< 4; k++){

            tx = que[head].x + next[k][0];

            ty = que[head].y + next[k][1];

            //越界

            if(tx<0 || tx>n-1 || ty<0 || ty>n-1) continue;

            //不是平地？以前走过了？

            if(a[tx][ty]!='.' || book[tx][ty]!=0) continue;

            //这个点可以走，并且没走过，就标记为走过了，然后入队

            book[tx][ty] = 1;

            que[tail].x = tx;

            que[tail].y = ty;

            tail++;

            sum = getnum(tx, ty);

            if(sum > max){

                max = sum;

                mx = tx;

                my = ty;

            }

        }

        //这个点的上下左右都看过了，就出队

        head++;

    }

    完整的代码如下：

#include<stdio.h>

struct Note{

    int x;

    int y;

};

char a[20][20];

//获取点（i, j）可以炸死多少敌人。

int getnum(int i, int j);

void main(){

    struct Note que[401];

    int head=1, tail=1;

    int book[20][20] = {0};

    int i, k, tx, ty, startx, starty, sum, max=0, mx, my, m, n;

    int next[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    //地图长n，宽m，起始位置坐标为startx，starty

    scanf("%d %d %d %d", &n, &m, &startx, &starty);

    for(i=0; i<n; i++){

        printf("Line : %d", i);

        scanf("%s", a[i]);

    }

    //起点入队

    que[tail].x = startx;

    que[tail].y = starty;

    tail++;

    book[startx][starty] = 1;

    max = getnum(startx, starty);

    mx = startx;

    my = starty;

    //广度优先搜索的核心部分

    while(head < tail){

        for(k = 0; k< 4; k++){

            tx = que[head].x + next[k][0];

            ty = que[head].y + next[k][1];

            //越界

            if(tx<0 || tx>n-1 || ty<0 || ty>n-1) continue;

            //不是平地？以前走过了？

            if(a[tx][ty]!='.' || book[tx][ty]!=0) continue;

            //这个点可以走，并且没走过，就标记为走过了，然后入队

            book[tx][ty] = 1;

            que[tail].x = tx;

            que[tail].y = ty;

            tail++;

            sum = getnum(tx, ty);

            if(sum > max){

                max = sum;

                mx = tx;

                my = ty;

            }

        }

        //这个点的上下左右都看过了，就出队

        head++;

    }

    printf("炸弹放在%d,%d的位置，可以炸死%d人", mx, my, max);

}

int getnum(int i, int j){

    int x, y, sum=0;

    //统计点(i, j)的左边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        x--;

    }

    //统计点(i, j)的右边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        x++;

    }

    //统计点(i, j)的上边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        y--;

    }

    //统计点(i, j)的下边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        y++;

    }

    return sum;

}

输入：第一次要求输入地图的长、宽、起始X坐标、起始Y坐标：13 13 3 3

第二次要求输入的就是地图了，每次一行，如下

#############

#GG.GGG#GGG.#

###.#G#G#G#G#

#.......#..G#

#G#.###.#G#G#

#GG.GGG.#.GG#

#G#.#G#.#.#.#

##G...G.....#

#G#.#G###.#G#

#...G#GGG.GG#

#G#.#G#G#.#G#

#GG.GGG#G.GG#

#############

输出：炸弹放在7，11的位置，可以炸死10人.

Ps:代码案例来源于《啊哈！算法》一书

炸弹人游戏本篇用广度优先搜索来解决，也可以深度优先搜索来实现。关于《深度优先搜索实现炸弹人游戏》点击查看

    什么是深度优先搜索？理解深度优先搜索的关键在于解决“当前如何做”，至于“下一步如何做”和“当前如何做是一样的做法”。深度优先搜索是Depth First Search, DFS。基本模型如下：

void dfs(int step){

    边界判断

    循环遍历去尝试每一种可能for(int i=0; i<n; i++){

        继续下一步dfs(step + 1);

    }

}

    下面看一个实例。我们有三个数字，1，2，3.求这三个数字的所有可能的搭配。那么，答案就是123，132，213，231，312，321共6种。我给出的答案顺序，也是深度优先搜索的顺序。

    假设我们有1，2，3的三张牌，地上有编号为一、二、三的三个纸箱。我们每次都把手中最小的牌放到箱子里，然后走到下一个箱子。

    第一步：在一号箱子面前，放入最小的手牌1，然后前进一步。此时手牌是2和3。判断边界（手牌是否为空）。

    第二步：在二号箱子面前，放入最小的手牌2，然后前进一步。此时手牌是3。判断边界（手牌是否为空）。

    第三步：在三号箱子面前，放入最小的手牌3，然后前进一步，此时手牌是空。判断边界（手牌是否为空）。

    第四步：手牌为空，触发边界条件。遍历打印箱子中的数字，结果是123。

    第五步：取出三号箱子的牌，后退一步。此时手牌是3。

    第六步：取出二号箱子的牌，此时手牌是2和3，2已经放过了，所以放3，然后前进一步。此时手牌是2。判断边界（手牌是否为空）。

    第七步：在三号箱子面前，放入最小手牌2，然后前进一步，此时手牌是空。判断边界（手牌是否为空）。

    第八步：手牌为空，触发边界条件。遍历打印箱子中的数字，结果是132。

    第九步：取出三号箱子的牌，后退一步。此时手牌是2。

    第十步：取出二号箱子的牌，此时手牌是2和3，2和3都已经放过了，所以再退一部。此时手牌是2。判断边界（手牌是否为空）。

    第十一步：取出一号箱子的牌，此时手牌是1，2和3，1以及放过了，所以放剩下的最小手牌，就是2，然后前进一步，此时手牌是1，3。判断边界（手牌是否为空）。

    第十二步：在二号箱子面前，放入最小的手牌1，然后前进一步。此时手牌是3。判断边界（手牌是否为空）。

    第十三步：在三号箱子面前，放入最小的手牌3，然后前进一步，此时手牌是空。判断边界（手牌是否为空）。

    第十四步：手牌为空，触发边界条件。遍历打印箱子中的数字，结果是213。

    ………………………………………………………………………………

    恩，就是这样子，直接上代码了。C版本的深度优先遍历的模型。

    Ps：本实例和代码均来自《啊哈！算法》一书。不过上面的过程是我自己手打原创哦^_^

#include <stdio.h>

void dfs(int step);

int a[10], book[10], n;

int main(){

    //1-9的整数

    scanf("%d", &n);

    //从第一个箱子开始。直接从下标1开始。0不要了。

    dfs(1);

}

void dfs(int step){

    int i;

    //已经到最后一个箱子了。

    if(step == n+1){

        for(i=1; i<=n; i++){

            printf("%d", a[i]);

        }

        printf("\n");

    }

    //在第step个箱子面前，按照1，2，3...n的顺序一一尝试

    for(i=1; i<=n; i++){

        //等于0就是i还没有使用，还在手里。

        if(book[i] == 0){

            //使用i

            a[step] = i;

            //标记i已经使用

            book[i] = 1;

            //前进一步

            dfs(step + 1);

            //回收step箱子里的牌

            book[i] = 0;

        }

    }

}

快速排序，是最常用的排序算法，就是选择待排序的列表中的其中一个数字，作为基准数，然后把小于基准数的所有数字放到这个数的左边，大于这个数的所有数字放到基准数的右边。这个时候开始分为两部分，左边和右边。第一部分，在左边中选择一个数字作为基准数，把小于这个数字的放到这个数的左边，大于这个数的放到这个数的右边。第二部分，在右边中选择一个数字作为基准数，把小于这个数字的放到这个数的左边，大于这个数的放到这个数的右边。ok，很明显，递归！

快速排序的时间复杂度在最坏的情况下是O(N2)，因为和冒泡排序一样，需要两两交换。平均情况下，快速排序的时间复杂度是O(NlogN)。

下面是C语言的代码

#include <stdio.h>

void quickSort(int left, int right, int *rank);

int main(){

    int i, j, num, score, tmp;

    printf("How many?\n");

    scanf("%d", &num);

    int rank[num];

    for(i=0; i<num; i++){

        printf("Enter Score:\n");

        scanf("%d", &score);

        //我们的试卷是0-100分的哦

        if(score<0 || score > 100){

            printf("Error");

            return 1;

        }

        rank[i] = score;

    }

    printf("Rank:\n");

    quickSort(0, num-1, rank);

    for(i=0; i<num; i++){

        printf("%d,", rank[i]);

    }

    return 0;

}

void quickSort(int left, int right, int *rank){

    if(left > right){

        return;

    }

    int i, j, t, tmp;

    i = left;

    j = right;

    t = rank[left];

    while(i!=j){

        while(rank[j]>=t && i<j)

            j--;

        while(rank[i]<=t && i<j)

            i++;

        if(i < j){

            tmp = rank[j];

            rank[j] = rank[i];

            rank[i] = tmp;

        }

    }

    rank[left] = rank[i];

    rank[i] = t;

    quickSort(left, i-1, rank);

    quickSort(i+1, right, rank);

}

冒泡排序是最被人熟知的排序算法。什么是冒泡排序？冒泡排序的特点是好邻居好说话，核心思想是一个每次比较两个相邻的元素，如果他们的大小顺序反了，就把他们交换过来。N个数就有N-1轮，每一轮把一个数字放在它正确的位置上。冒泡排序时间复杂度是O(N2)。C语言代码如下：

#include <stdio.h>

int main(){

    int i, j, num, score, tmp;

    printf("How many?\n");

    scanf("%d", &num);

    int rank[num];

    for(i=0; i<num; i++){

        printf("Enter Score:\n");

        scanf("%d", &score);

        //我们的试卷是0-100分的哦

        if(score<0 || score > 100){

            printf("Error");

            return 1;

        }

        rank[i] = score;

    }

    printf("Rank:\n");

    //冒泡排序

    for(i=0; i<num-1; i++){

        for(j=0; j<num-i; j++){

            if(rank[j] > rank[j+1]){

                tmp = rank[j];

                rank[j] = rank[j+1];

                rank[j+1] = tmp;

            }

        }

    }

    for(i=0; i<num; i++){

        printf("%d,", rank[i]);

    }

    return 0;

}