撕烂数据爆锤算法：广度、深度优先搜索例题之炸弹人-物联网技术文章-傲云油气装备网

啰啰嗦嗦

理解知识最有效的方式之一就是多刷题，在解题的过程中我们可能会更加容易记忆和理解知识点，我们能够了解到其在题目中的具体运用方式。通过实打实的上手编程，带来的好处不言而喻。如果你仅限于从书中看懂或者从教学视频中听懂，而不亲手去实现它，这些知识很难被真正的掌握。当你一字一字地完整地码下来时，你会发现其实有很多错误是你平时学习的时候注意不到的。只有经过大量实战练习，你才会对自己的不足有所了解。当然，小编也是刚学习不久，若有什么不足之处，还望各位大佬海涵啦！
同是天涯码字猿，
共勉，共勉~~~

题干

炸弹人小鑫拥有一个威力巨大的炸弹，它能炸掉其上、下、左、右四个方向上的所有气球，但是不能炸掉坚硬的墙壁。现在小鑫正处于一个高n，宽m的地图里，地图中有墙、空地和气球（规定用1表示墙，0表示空地，2表示气球）。小鑫只能在空地上行走，且只能向上下左右四个方向行走，更不可走出地图边界。试问小鑫应该把炸弹安放在何处，才能使炸弹炸掉的气球数最多呢？发挥你的聪明才智，帮帮小鑫吧！（注：炸弹只能放在空地上）

输入：
第一行输入n（0<n<100）,m（0<m<100）
输入n行每行m个（0或1或2）分别用来表示空地、墙、气球

输出：
炸弹应该安放在: 位置坐标（x，y）炸掉气球数为: 整数

输入示例：
13 13
1 1 1 1 1 1 1 1 1 1 1 1 1
1 2 2 0 2 2 2 1 2 2 2 0 1
1 1 1 0 1 2 1 2 1 2 1 2 1
1 0 0 0 0 0 0 0 1 0 0 2 1
1 2 1 0 1 1 1 0 1 2 1 2 1
1 2 2 0 2 2 2 0 1 0 2 2 1
1 2 1 0 1 2 1 0 1 0 1 1 1
1 1 2 0 0 0 2 0 0 0 0 0 1
1 2 1 0 1 2 1 1 1 0 1 2 1
1 0 0 0 2 1 2 2 2 0 2 2 1
1 2 1 0 1 2 1 2 1 0 1 2 1
1 2 2 0 2 2 2 1 2 0 2 2 1
1 1 1 1 1 1 1 1 1 1 1 1 1
5 4

输出示例：
炸弹应该安放在: (10,10) 炸掉气球数为: 8

解法一：广度优先搜索

（C++实现）

定义头文件

//头文件
#include<iostream>
using namespace std;

宏定义

//宏定义
#define UNDEFIND -231231 //不存在的数
#define MAX_NODE_NUM 100 //标记位置数量的最大值
#define MAX_MAP_SIZE 100 //地图宽和高的最大值
#define MAX_KEEPNODE_NUM 100 //保存位置信息数的最大值

定义炸弹人类

typedef class Node{//炸弹人类，用于表示炸弹人及炸弹相关信息

friend class NodeQueue; //设置类友元

//属性
private:
	int x;  //炸弹人的x坐标
	int y;  //炸弹人的y坐标
	int over_num;  //炸弹炸掉气球的个数
	Node* next;    //指向下一位置信息的指针

//方法
public:
	Node(){//构造函数，初始化属性
		this->x=UNDEFIND;
		this->y=UNDEFIND;
		over_num=UNDEFIND;
		next=NULL;
	}

	Node(int x,int y,int num){//构造函数，给属性赋值
		this->x=x;
		this->y=y;
		over_num=num;
		next=NULL;
	}

	int getX(){//返回x坐标
		return x;
	}

	int getY(){//返回y坐标
		return y;
	}

	int getOverNum(){//返回炸掉气球个数
		return over_num;
	}

	void destory(){//销毁对象
		delete this;
	}
}Node,*Pnode;    //typedef用于取别名

定义队列类

int k=0;    //Keep数组的索引键值
Pnode Keep[MAX_KEEPNODE_NUM];   //保留所有炸弹人能到达且能安放炸弹的位置的信息

typedef class NodeQueue{//队列类，用于暂时存储炸弹人走过且能安放炸弹的位置的信息

//属性
private:
	Pnode head;  //队头
	Pnode last;  //队尾

public:
	NodeQueue(){//构造函数，初始化队头、队尾结点
		last=head=new Node();
	}

	bool isEmpty(){//判断队列是否为空
		return head->next==NULL;
	}

	void add(int x,int y,int num){//入队
		Pnode N;
		N=new Node(x,y,num);
		Keep[k++]=new Node(x,y,num); //将位置信息存入Keep数组
		last->next=N;
		last=N;
		return;
	}

	Pnode remove(){//出队
		Pnode h,g;
		h=head->next;
		g=new Node(h->getX(),h->getY(),h->getOverNum());
		head->next=h->next;
		if(head->next==NULL)
			last=head;
		delete h;
		return g;
	}
	void destory(){//销毁队列
		delete head;
	}
}NQueue,*Pqueue;

定义游戏操作类

class BombMan{//游戏操作类，用于设置地图、实施安放炸弹相关操作

//属性
private:
	int n;   //地图高度
	int m;   //地图宽度
	int Next[4][2];  //炸弹人行走方向，上->右->下->左
    int Map[MAX_MAP_SIZE][MAX_MAP_SIZE];   //地图数组，值为1表示墙，0表示空地，2表示气球
    int Sign[MAX_NODE_NUM][MAX_NODE_NUM];  //标记数组，用来标记位置信息，值为1表示该位置已经走过，为0表示未走过

//私有方法
private:
    void destoryKeep(){//销毁keep数组中的所有结点
	    int i;
	    for(i=0;i<k-1;i++)
		    Keep[i]->destory();
	    return;
	}

    int getOverNums(int x,int y){//返回炸弹安放在（x,y）时，能炸掉的气球数
		int i,j,num;
	    num=0;
		//记录各个方向上能炸掉的气球数
	    for(i=x-1,j=y;i>0 && (Map[i][j]==2 || Map[i][j]==0);i--)//向上
		    if(Map[i][j]==2)
			    num++;
	    for(i=x,j=y+1;j<=m && (Map[i][j]==2 || Map[i][j]==0);j++)//向右
		    if(Map[i][j]==2)
		        num++;
	    for(i=x+1,j=y;i<=n && (Map[i][j]==2 || Map[i][j]==0);i++)//向下
		    if(Map[i][j]==2)
		        num++;
	    for(i=x,j=y-1;j>0 && (Map[i][j]==2 || Map[i][j]==0);j--)//向左
		    if(Map[i][j]==2)
		        num++;
	    return num;
	}

//公共方法
public:
	BombMan(){//初始化Sign数组和Keep数组
		int i,j;
		for(i=0;i<MAX_NODE_NUM;i++)
			for(j=0;j<MAX_NODE_NUM;j++)
		        Sign[i][j]=0;
		Next[0][0]=-1;
		Next[0][1]=0;
		Next[1][0]=0;
		Next[1][1]=1;
		Next[2][0]=1;
		Next[2][1]=0;
		Next[3][0]=0;
		Next[3][1]=-1;
	}

	void createMap(){//创建地图
	    int i,j;
	    cin>>n>>m;
	    for(i=1;i<=n;i++)
		    for(j=1;j<=m;j++)
			    cin>>Map[i][j];
	    return;
	}
	
    void setStartPlace(){//设置起始点
	    Pnode N;
	    int x,y,num;
	    cin>>x>>y;
	    if(x<1 || x>n || y<1 || y>m)
		{
		    cout<<endl<<"起始地点值有误，游戏结束！"
			    <<endl<<endl;
		    exit(-1);
		}
	    else if(Map[x][y]!=0)
		{
		    cout<<endl<<"起始地点不是空地，游戏结束！"
			    <<endl<<endl;
		    exit(-1);
		}
	    num=getOverNums(x,y);
	    N=new Node(x,y,num);
	    Keep[k++]=N;   //将炸弹人起始位置信息保存在Keep数组中
	    Sign[x][y]=1;  //该位置标记走过
	    return;
	}
	
    void layBomb(){//通过广度优先搜索，炸弹人走一遍每个能走到的位置 （算法核心）
	    Pnode h;
	    Pqueue Q;
	    int i,num,tx,ty;
	    Q=new NQueue();
	    num=getOverNums(Keep[k-1]->getX(),Keep[k-1]->getY());
	    Q->add(Keep[k-1]->getX(),Keep[k-1]->getY(),num);      //将起始点位置信息入队
	    while(!Q->isEmpty())
		{
		    h=Q->remove();  //出队，得到炸弹人当前位置信息
		    for(i=0;i<4;i++)//炸弹人下一步行走的四个方向，都尝试走一遍，能走则将这个方向的位置入队
			{
				//得到下一步位置
			    tx=h->getX()+Next[i][0];
			    ty=h->getY()+Next[i][1];
			    if(tx<1 || tx>n || ty<1 || ty>m)  //判断炸弹人下一步位置是否越界，越界则进入另外方向的行走
				    continue;
			    if(Map[tx][ty]==0 && Sign[tx][ty]==0)  //判断炸弹人下一步位置是否能走（需未被标记且是空地）
				{
				    Sign[tx][ty]=1;  //该位置标记走过
				    num=getOverNums(tx,ty);  
				    Q->add(tx,ty,num);   //将该位置入队
				}
			}
		}
	    Q->destory();
	    return;
	}

    void getMaxOverNumNode(){//找到炸弹能炸掉最多气球的安放点，并输出结果
		int i,pos;
	    pos=0;
	    for(i=1;i<k;i++)
		    if(Keep[pos]->getOverNum()<Keep[i]->getOverNum())
			    pos=i;
	    cout<<endl<<"炸弹应该安放在: ("
		    <<Keep[pos]->getX()<<","<<Keep[pos]->getY()<<") "
		    <<" 炸掉气球数为: "<<Keep[pos]->getOverNum()
		    <<endl<<endl;
	    destoryKeep();
	    return;
    }

	void destory(){//销毁对象
		delete this;
	}
};

测试函数

//测试
void Test()
{
	BombMan* B=new BombMan();
	B->createMap();
	B->setStartPlace();
	B->layBomb();
	B->getMaxOverNumNode();
	B->destory();
	return;
}

int main()
{
	Test();
	system("pause");
	return 0;
}

运行结果

解法二：深度优先搜索

（大致步骤与解法一类似，请先理解解法一）

定义头文件

//头文件
#include<iostream>
using namespace std;

宏定义

//宏定义
#define UNDEFIND -231231 //不存在的数
#define MAX_NODE_NUM 100 //标记位置数量的最大值
#define MAX_MAP_SIZE 100 //地图宽和高的最大值
#define MAX_KEEPNODE_NUM 100 //保存位置信息数的最大值

定义炸弹人类

typedef class Node{//炸弹人类，用于表示炸弹人及炸弹相关信息

friend class NodeQueue; //设置类友元

//属性
private:
	int x;  //炸弹人的x坐标
	int y;  //炸弹人的y坐标
	int over_num;  //炸弹炸掉气球的个数
	Node* next;    //指向下一位置信息的指针

//方法
public:
	Node(){//构造函数，初始化属性
		this->x=UNDEFIND;
		this->y=UNDEFIND;
		over_num=UNDEFIND;
		next=NULL;
	}

	Node(int x,int y,int num){//构造函数，给属性赋值
		this->x=x;
		this->y=y;
		over_num=num;
		next=NULL;
	}

	int getX(){//返回x坐标
		return x;
	}

	int getY(){//返回y坐标
		return y;
	}

	int getOverNum(){//返回炸掉气球个数
		return over_num;
	}

	void destory(){//销毁对象
		delete this;
	}
}Node,*Pnode;

定义游戏操作类

int k=0;
Pnode Keep[MAX_KEEPNODE_NUM];

class BombMan{
private:
	int n;
	int m;
	int Next[4][2];
    int Map[MAX_MAP_SIZE][MAX_MAP_SIZE];
    int Sign[MAX_NODE_NUM][MAX_NODE_NUM];

private:
	void destoryKeep(){
	    int i;
	    for(i=0;i<k-1;i++)
		    Keep[i]->destory();
	    return;
	}

	int getOverNums(int x,int y){
		int i,j,num;
	    num=0;
	    for(i=x-1,j=y;i>0 && (Map[i][j]==2 || Map[i][j]==0);i--)
		    if(Map[i][j]==2)
			    num++;
	    for(i=x,j=y+1;j<=m && (Map[i][j]==2 || Map[i][j]==0);j++)
		    if(Map[i][j]==2)
		        num++;
	    for(i=x+1,j=y;i<=n && (Map[i][j]==2 || Map[i][j]==0);i++)
		    if(Map[i][j]==2)
		        num++;
	    for(i=x,j=y-1;j>0 && (Map[i][j]==2 || Map[i][j]==0);j--)
		    if(Map[i][j]==2)
		        num++;
	    return num;
	}

public:
	BombMan(){
		int i,j;
		for(i=0;i<MAX_NODE_NUM;i++)
			for(j=0;j<MAX_NODE_NUM;j++)
		        Sign[i][j]=0;
		Next[0][0]=-1;
		Next[0][1]=0;
		Next[1][0]=0;
		Next[1][1]=1;
		Next[2][0]=1;
		Next[2][1]=0;
		Next[3][0]=0;
		Next[3][1]=-1;
	}

	void createMap(){
	    int i,j;
	    cin>>n>>m;
	    for(i=1;i<=n;i++)
		    for(j=1;j<=m;j++)
			    cin>>Map[i][j];
	    return;
	}

    void setStartPlace(){
	    Pnode N;
	    int x,y,num;
	    cin>>x>>y;
	    if(x<1 || x>n || y<1 || y>m)
		{
		    cout<<endl<<"起始地点值有误，游戏结束！"
			    <<endl<<endl;
		    exit(-1);
		}
	    else if(Map[x][y]!=0)
		{
		    cout<<endl<<"起始地点不是空地，游戏结束！"
			    <<endl<<endl;
		    exit(-1);
		}
	    num=getOverNums(x,y);
	    N=new Node(x,y,num);
	    Keep[k++]=N;
	    Sign[x][y]=1;
	    return;
	}

	Pnode getKeepFirstNode(){
		return Keep[k-1];
	}

    void layBomb(Pnode h){//通过深度优先搜索，炸弹人走一遍每个能走到的位置 （算法核心） 
		Pnode p;
		int i,tx,ty,num;
    	for(i=0;i<4;i++)
		{
	 		tx=h->getX()+Next[i][0];
			ty=h->getY()+Next[i][1];
			if(tx<1 || tx>n || ty<1 || ty>m)
				continue;
			if(Map[tx][ty]==0 && Sign[tx][ty]==0)
			{
				Sign[tx][ty]=1;
				num=getOverNums(tx,ty);
			    p=new Node(tx,ty,num);
				Keep[k++]=p;//保存能走且能安放炸弹的位置信息
				layBomb(p);//递归调用，炸弹人移到这个方向上的下一步的位置
			}
		}
		return;
	}

    void getMaxOverNumNode(){
		int i,pos;
	    pos=0;
	    for(i=1;i<k;i++)
		    if(Keep[pos]->getOverNum()<Keep[i]->getOverNum())
			    pos=i;
	    cout<<endl<<"炸弹应该安放在: ("
		    <<Keep[pos]->getX()<<","<<Keep[pos]->getY()<<") "
		    <<" 炸掉气球数为: "<<Keep[pos]->getOverNum()
		    <<endl<<endl;
	    destoryKeep();
	    return;
    }

	void destory(){
		delete this;
	}

};

测试函数

//测试
void Test()
{
	BombMan* B=new BombMan();
	B->createMap();
	B->setStartPlace();
	B->layBomb();
	B->getMaxOverNumNode();
	B->destory();
	return;
}

int main()
{
	Test();
	system("pause");
	return 0;
}

运行结果

文末

菜鸟小编带你撕烂数据锤爆算法，关于两种优先搜索算法的具体知识正在更新中，敬请期待！

小小推荐

撕烂数据爆锤算法系列：
单链表
循环链表
内排序之插入算法
内排序之交换算法

程序人生系列：
大一总结：一路走来，从迷茫到渴望

感谢浏览，你们的支持是我最大的动力，拜~~

• kotlin ViewPager + TabLayout + Fragment（优	• composer拓展包开发
• 腾讯地图，附着物的扩散水波纹效果	• Android 小应用之一个activity实现简易手电筒（
• Android的webView应用与js互调app混合开发用例	• arm net-snmp使用

• Esp8266天猫精灵_RGB灯_非点灯平台	• STM32F103 串口1和串口3对发数据配合蓝牙模块
• TMS570学习【1】了解什么是TMS570	• 新闻稿 \| Qt公司收购froglogic公司以巩固市场领
• [Java]SpringBoot2整合mqtt服务器EMQ实现消息订	• 苹果群控投屏同步操作原理及运用的平台APP分享

• Esp8266天猫精灵_RGB灯_非点灯平台	• STM32F103 串口1和串口3对发数据配合蓝牙模块
• TMS570学习【1】了解什么是TMS570	• 新闻稿 \| Qt公司收购froglogic公司以巩固市场领
• [Java]SpringBoot2整合mqtt服务器EMQ实现消息订	• 苹果群控投屏同步操作原理及运用的平台APP分享
• STM32查询式按键输入[直接用寄存器]	• Ubuntu系统 USB设备端口绑定
• 2021-04-14 第四次按键输入实验	• Flutter扫码功能完美实现