上一章我们编写了一个小游戏:炸弹人游戏。使用广度优先搜索解决的,本章将用深度优先搜索来解决。
深度优先搜索的核心代码如下:说白了,就是一条路走到黑,然后回头倒着走看看有没有别的岔路口,不断递归。
深度优先搜索的核心代码如下:说白了,就是一条路走到黑,然后回头倒着走看看有没有别的岔路口,不断递归。
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:代码案例来源于《啊哈!算法》一书
上一篇:
算法七:广度优先搜索
友情提示:垃圾评论一律封号...