啊哈算法炸弹人游戏----深度优先搜索与广度优先搜索
在《炸弹人》游戏中，《定时炸弹》任务是一个极具挑战性的考验玩家策略性的环节。你的任务是在此模式下找到最佳投掷位置——即该定时炸弹具有十字形攻击范围（仅能以上下左右四个方向发射火焰），其爆炸范围受限于墙壁的存在。那么应该将这个定时炸弹放置在何处才能消灭最多的敌人？游戏地图如图所示（注意：投放点必须位于玩家可移动到的位置——因为玩家无法飞行），而墙或者敌人的阻挡都会影响到你的投掷效果。
2.解题思路：首先需要将问题进行抽象化处理。具体来说，
可以用二维数组来表示游戏地图，
其中*代表平地区域，
#代表墙阻挡，
$标识小怪的位置。
根据题目条件，
炸弹人的起始位置位于坐标(3,3)处。
我们的目标是在这个地图中找到一个最优的位置点，
该位置能够最大限度地消灭周围的小怪数量最多。
因此我们需要计算出，
在任意给定的(x,y)位置上放置炸弹时，
其能够造成最大的杀伤范围。
因此，在优先级列表中排在第一位的目标就是从数据库中提取地理位置信息；随后我们需要确定这些地理位置信息所对应的地点能够被多少次攻击到小怪群落
制作地图相对简单；计算小怪总数。
由于炸弹爆炸仅会产生十字形伤害范围，
因此，在(x,y)位置放置炸弹所带来的伤害范围内的小怪总数即为该点上行、下行、左行、右行方向上未碰到墙壁时遇到的小怪之和。
C++程序如下：
#include "iostream"
using namespace std;
#include "vector"
#include "string"
class game_boom//声明该类
{
public:
void game_map();//构建地图
int num_boom(int x, int y);//x,y为炸弹放置的位置
public:
vector<string> map;//地图属性
};
//具象问题抽象化，抽象出来地图与人物；用#代表墙，用*代表空地，用$来代表怪物
//地图是一个平面，所以用一个二维数组来代替
void game_boom::game_map()
{
string s0 = "#############";
string s1 = "#$$*$$$#$$$*#";
string s2 = "###*#$#$#$#$#";
string s3 = "#*******#**$#";
string s4 = "#$#*###*#$#$#";
string s5 = "#$$*$$$*#*$$#";
string s6 = "#$#*#$#*#*#*#";
string s7 = "##$***$*****#";
string s8 = "#$#*#$###*#$#";
string s9 = "#***$#$$$*$$#";
string s10 = "#$#*#$#$#*#$#";
string s11 = "#$$*$$$#$*$$#";
string s12 = "#############";
//已知地图是13*13的，所以针对该问题可以静态创建地图
map.push_back(s0);
map.push_back(s1);
map.push_back(s2);
map.push_back(s3);
map.push_back(s4);
map.push_back(s5);
map.push_back(s6);
map.push_back(s7);
map.push_back(s8);
map.push_back(s9);
map.push_back(s10);
map.push_back(s11);
map.push_back(s12);
}
int game_boom::num_boom(int i, int j)//统计炸弹的威力
{
int res = 0;
//统计向上的威力（炸死怪物的个数）
int x = i;//必须用临时变量将 i,j接过来，因为每一次统计的时候 都是从原位置出发，不能改变
int y = j;//防止初始位置发生变化，造成统计错误
while (map[x][y] != '#')//表明没有撞到墙
{
if (map[x][y] == '$')
{
res++;
}
x--;//向上走
}
//统计向下的威力（炸死怪物的个数）
x = i;
y = j;//防止初始位置发生变化，造成统计错误
while (map[x][y] != '#')//表明没有撞到墙
{
if (map[x][y] == '$')
{
res++;
}
x++;//向下走
}
//统计向左的威力（炸死怪物的个数）
x = i;
y = j;//防止初始位置发生变化，造成统计错误
while (map[x][y] != '#')//表明没有撞到墙
{
if (map[x][y] == '$')
{
res++;
}
y--;//向左走
}
//统计向右的威力（炸死怪物的个数）
x = i;
y = j;//防止初始位置发生变化，造成统计错误
while (map[x][y] != '#')//表明没有撞到墙
{
if (map[x][y] == '$')
{
res++;
}
y++;//向右走
}
return res;
}
AI写代码有了地图模型,我们掌握了每个坐标点(x,y)上布置炸弹时能够摧毁的小怪数量信息,因此下一步就是要确定炸弹布置的具体位置了；
当前时段内炸弹人出现在坐标（3,3）位置上。由于其每次移动仅限于上下左右四个方向，并且无法穿越墙壁以及避开小怪兽，在每一次搜索行动中它都必须遵循这一限制条件。
所以，在我们的搜索策略中也融入了多维度的创新思维，在某些场景下可以采取直行至终点的方式继续探索直至遇到敌人或触壁受挫（俗称为'不撞南墙不回头'"）
即深度优先搜索
在出发前需评估该位置是否已被访问过（避免重复路线），因为本问题的核心目标是找到一个位置使得炸弹的威力最大化。无需对已评估的位置进行再次计算，并记录每个位置上炸弹的威力值与目前的最大值比较；如果其数值超过目前的最大值，则更新该位置的数据。
在其中关键在于如何判定是否重复。我们可以使用一个二维数组来对应地图，在初始化时, 每个元素设为0以表示地图上的所有位置均未被访问过.当我们经过某一点时, 则将其标记为已访问.
上下左右的移动 可以用一个数组表示
int next[4][2] = { {-1,0},{+1,0},{0,-1},{0,1} }; //小人可以扩展的方向，上下左右
之后，在应用深度搜索DFS时最为关键的就是处理当前这一步的工作内容,由于后续步骤与当前步骤的操作方式完全一致
伪代码：
第一步操作：我们选择初始坐标位置为(3,3)，随后对该位置设置标志位以表明该位置已被访问过。接着进行如下操作：评估位于此坐标的炸弹破坏力并将其记录入最大破坏力数值中。为了确保数据完整性，在完成所有计算后需将当前处理的位置坐标值存储起来作为后续分析的基础数据源。
开始循环向上下左右四个方向分别尝试
{
判断扩展的点是否越界，查出地图，查出则进行下一个方向的尝试
确定该点是否已被访问过，并同时确定该点是否为平面区域（因为只有平面区域才能放置炸弹）。若该点尚未被访问过，并且具备放置炸弹的条件
则以此点为初始点 进一步 按原策略搜索
}
搜索完毕后返回
完整程序如下：（需要将上面的地图初始化程序保存为game_map.h文件）
#include "iostream"
using namespace std;
#include "vector"
#include "game_map.h"
//深度优先搜索是通过递归来实现的
//我们需要保存的信息是遍历过的以及该位置安装炸弹时炸死的怪物个数，所以需要一个新的数据类型
class Position//保存每一个位置和该点炸弹的威力
{
public:
void set_x_y_nums(int tx, int ty, int nums)
{
this->x = tx;
this->y = ty;
this->nums = nums;
}
public:
int x;
int y;
int nums;//炸死小人的个数
};
void DFS(int x, int y,game_boom Game/*游戏地图和炸弹威力计算*/,vector<vector<int>> &book/*标记某一点是否走过*/,Position &max_pos/*炸弹最大威力位置*/)
{
book[x][y] = 1;
int sum = Game.num_boom(x, y);
if (sum > max_pos.nums)
{
max_pos.nums = sum;
max_pos.x = x;
max_pos.y = y;
}
int next[4][2] = { {-1,0},{+1,0},{0,-1},{0,1} }; //小人可以扩展的方向，上下左右
//没有边界，边界即遍历完所有点
//开始循环
for (int k = 0;k < 4;k++)
{
int tx = x + next[k][0];
int ty = y + next[k][1];
if (tx < 0 || tx > 12 || ty < 0 || ty >12)
{
continue;
}
if (Game.map[tx][ty] == '*' && book[tx][ty] == 0)
{
//如果下一个点可以扩展，而且没有走过，则可以进一步扩展
DFS(tx,ty, Game, book, max_pos);
}
}
return;
}
int main()
{
game_boom Game;//开始游戏
Game.game_map();//创建地图
vector<int> v(13, 0);
vector<vector<int>> book(13, v);//book用来表示该位置是否走过
Position max_pos;
max_pos.set_x_y_nums(3,3,0);
DFS(3, 3, Game, book, max_pos);
printf("炸弹应该安放的位置是(%d,%d),它能够炸死%d个小怪\n",max_pos.x,max_pos.y,max_pos.nums);
system("pause");
return 0;
}
AI写代码
当然，我们可以不那么轴，不一条路走到黑，
即广度优先搜索：
也就是我们从初始位置出发进行扩展操作。具体来说，在第一阶段中我们会依次向上、向下、向左、向右四个方向进行路径探索，并完成一轮完整的扩展过程。随后我们需要将焦点移至初始位置的上方节点，并重新启动扩展流程：首先处理该节点的所有上下左右邻居节点（这些关键点需记录以便后续操作），然后依次遍历初始位置下方节点周围的各个方向进行同样的探索。
发现没有？这其实就是一个序列系统：从起始点出发（进行入队操作），检查并加入所有与起始点相邻的位置（上下左右四个方向）。随后取出起始点，并接着扩展刚被取出的那个节点的所有未被访问过的位置（即当前序列的第一个新节点），同样将这些新加入的位置标记为已访问并记录下来。如此反复循环往复，直到整个序列已经没有任何新增可执行的操作为止。
伪算法：
将初始位置加入队列中，并对该位置进行已访问状态设置为1；随后计算该位置处炸弹的最大杀伤范围，并将计算结果进行存储。
从上至下、左至右进行循环遍历，在每次操作中均以队列中的第一个元素作为起始点，并将新位置加入队列中，并且在每次扩展时需先检查是否越界。判断能否放置炸弹和是否已经被访问过之后，在满足特定条件下需要比较该位置的最大破坏力与当前记录的最大破坏力之间的关系：若前者更大，则更新当前最大破坏力值。
然后队首元素出队
如此往复循环
注释说明：
此程序基于上一阶段的地图初始化流程进行设计，
并且必须包含game_boom.h文件
#include "iostream"
using namespace std;
#include "vector"
#include "queue"
#include "game_map.h"
//广度优先搜索是借助队列来完成的
//我们需要保存的信息是遍历过的以及该位置安装炸弹时炸死的怪物个数，所以需要一个新的数据类型
class Position
{
public:
void set_x_y_nums(int tx, int ty, int nums)
{
this->x = tx;
this->y = ty;
this->nums = nums;
}
public:
int x;
int y;
int nums;//炸死小人的个数
};
int main()
{
game_boom Game;//开始游戏
Game.game_map();//创建地图
vector<int> v(13, 0);
vector<vector<int>> book(13,v);//book用来表示该位置是否走过
int next[4][2] = {{-1,0},{+1,0},{0,-1},{0,1}}; //小人可以扩展的方向，上下左右
queue<Position> Queue;//构建一个装小人走到位置的队列
//小人的初始位置 入队列
int x = 3;
int y = 3;
//统计目前能炸死的怪物个数
int nums = Game.num_boom(x,y);
Position p;
p.set_x_y_nums(x,y,nums);//设置对象p的属性
Queue.push(p);
book[3][3] = 1;//将（3,3）位置标记为已经走过，之后不再走该位置
Position max_pos;
max_pos.set_x_y_nums(x,y,nums);//设计一个对象 保存 能炸死最多怪物的点
while (!Queue.empty())//开始扩展，找其可以一步走到的地方
{
for (int k = 0;k < 4;k++)//向上下左右四个方向扩展
{
int tx = Queue.front().x + next[k][0];
int ty = Queue.front().y + next[k][1];
//(tx,ty)表示新的位置，在新的位置入队列之前我们需要判断是否越界，该点点能否到达，或者是否已经到过
if(tx < 0 || tx > 12 || ty <0 || ty >12)
{
continue;
}
if (Game.map[tx][ty] == '*' && book[tx][ty] == 0)//可以入队列等待下一次扩展
{
book[tx][ty] = 1;
int tnums = Game.num_boom(tx,ty);
Position tmp;
tmp.set_x_y_nums(tx, ty, tnums);
if (tnums > max_pos.nums)//如果该位置能炸死的怪物数比目前目前记录的多，则替换max_pos
{
max_pos.set_x_y_nums(tx, ty, tnums);
}
Queue.push(tmp);
}
}
Queue.pop();//出队，因为该点已经扩展完毕，开始扩展下一个点
}
printf("炸弹应该安放的位置是(%d,%d),它能够炸死%d个小怪\n", max_pos.x, max_pos.y, max_pos.nums);
system("pause");
return 0;
}
AI写代码
参考：《啊哈算法》