什么是广度优先搜索?广度优先搜索也称为宽度优先搜索,一层一层不断的扩展来达到搜索的目的。以一个点为中心,将上下左右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:代码案例来源于《啊哈!算法》一书
炸弹人游戏本篇用广度优先搜索来解决,也可以深度优先搜索来实现。关于《深度优先搜索实现炸弹人游戏》点击查看
Bslanteefs On pharmacie boulogne billancourt...
Bslanteefs On therapie streaming, pharmacie ...
EElemeecowl On pharmacie lafayette belfort, a...
BInfurnese On pharmacie simo argenteuil, pha...
BInfurnese On pharmacie lafayette amiens tel...
Reply: India On 2020-08-06 05:30:08
generic bimatoprost ophthalmic solution https://www.jueriy.com/
回复