广度优先搜索_什么是广度优先搜索_广度优先搜索的优缺点 - Lane Blog

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

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;

}

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

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;

}

Read full article from 广度优先搜索_什么是广度优先搜索_广度优先搜索的优缺点 - Lane Blog