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

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

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


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

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:代码案例来源于《啊哈!算法》一书

标签: 算法, 深度优先搜索

仅有一条评论

  1. sr030

    请问在dfs()函数中:

    //判断墙和是否走过

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

    book[tx][ty] = 1;

    dfs(tx, ty);

    这里为什么不需要将 book[tx][ty] 置0了呢?想不明白。

添加新评论