算法八:炸弹人游戏之深度优先搜索
上一章我们编写了一个小游戏:炸弹人游戏。使用广度优先搜索解决的,本章将用深度优先搜索来解决。
《关于广度优先搜索解决炸弹人游戏和炸弹人游戏的描述》点击查看
《什么是深度优先搜索》点击查看
深度优先搜索的核心代码如下:说白了,就是一条路走到黑,然后回头倒着走看看有没有别的岔路口,不断递归。
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:代码案例来源于《啊哈!算法》一书
请问在dfs()函数中:
//判断墙和是否走过
if(a[tx][ty] != '.' || book[tx][ty] != 0) continue;
book[tx][ty] = 1;
dfs(tx, ty);
这里为什么不需要将 book[tx][ty] 置0了呢?想不明白。