什么是广度优先搜索?广度优先搜索也称为宽度优先搜索,一层一层不断的扩展来达到搜索的目的。以一个点为中心,将上下左右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:代码案例来源于《啊哈!算法》一书
炸弹人游戏本篇用广度优先搜索来解决,也可以深度优先搜索来实现。关于《深度优先搜索实现炸弹人游戏》点击查看
上一篇:
算法六:深度优先搜索
下一篇:
算法八:炸弹人游戏之深度优先搜索
友情提示:垃圾评论一律封号...