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

算法七：广度优先搜索

Clicks: 7189 Date: 2014-11-11 21:56:38 Power By 李轩Lane
算法广度优先排序
        什么是广度优先搜索？广度优先搜索也称为宽度优先搜索，一层一层不断的扩展来达到搜索的目的。以一个点为中心，将上下左右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:代码案例来源于《啊哈！算法》一书

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