本文主要是介绍炸弹人 bfs + dfs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
bfs
#include<iostream>
using namespace std;
// 炸弹人 在哪里放炸弹会炸死最多的人？
// .代表是敌人1 # 代表墙壁 2 * 代表为空 0
// 思路是 dfs 和bfs
//最开始先创建地图
int a[51][51];//50*50的地图
int n, m;
//bfs首先创建队列节点note 用来记录point的坐标
//其次创建一个用来记录最大答案的结构体
//因为要炸死敌人 所以要写一个函数 用来统计炸死了多少人 给一个坐标返回最多能炸死的人数
//用来标记是否重复走过
int book[51][51];
int directionX[] = { 1,-1,0,0 };
int directionY[] = { 0,0,1,-1 };int Boom(int x, int y)
{//向上搜索 遇到墙壁为止int sx = x;int sy = y;int sum = 0;//向上while ((x > 0 && x <= n && y > 0 && y <= m) && a[x][y] != 2 ){if (a[x][y] == 1){sum++;}x++;}//更新一下ovox = sx;y = sy;while ((x > 0 && x <= n && y > 0 && y <= m) && a[x][y] != 2){if (a[x][y] == 1){sum++;}y++;}x = sx;y = sy;while ((x > 0 && x <= n && y > 0 && y <= m) && a[x][y] != 2){if (a[x][y] == 1){sum++;}x--;}x = sx;y = sy;while ((x > 0 && x <= n && y > 0 && y <= m) && a[x][y] != 2){if (a[x][y] == 1){sum++;}y--;}x = sx;y = sy;return sum;
}struct ansMax
{int x, y;int maxNumb;//能炸死最大敌人的数值
}ans;struct note
{int x, y;
}bfsNote[2501];void bfs(int head,int tail)
{while (head < tail){for (int i = 0; i <= 3; i++){int tx = bfsNote[head].x + directionX[i];int ty = bfsNote[head].y + directionY[i];// cout << tx << " " << ty << endl;if (tx <= n && tx>0&&ty <= m && ty>0&&book[tx][ty]==0&&a[tx][ty]==0 //保证是空地){// cout << tx << " " << ty << endl;book[tx][ty] = 1;//标记bfsNote[tail].x = tx;bfsNote[tail].y = ty;tail++;int Thisnumb = Boom(tx, ty);if (Thisnumb > ans.maxNumb){// cout << tx << " " << ty << endl;ans.x = tx;ans.y = ty;ans.maxNumb = Thisnumb;}}}head++;//此节点已经用完 }
}
int main()
{cin >> n >> m;int head = 1;int tail = 1;book[1][1] = 1;bfsNote[tail].x = 1;bfsNote[tail].y = 1;tail++;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){cin >> a[i][j];}}
/* cout << Boom(4, 4);*/ans.x = 1;ans.y = 1;ans.maxNumb = Boom(ans.x, ans.y);
/* cout << ans.maxNumb;*/bfs(head, tail);cout << ans.x << " " << ans.y << " " << ans.maxNumb;
}
/*
4 4
0 2 1 1
0 0 1 1
0 0 0 1
1 0 0 0
*/
dfs
这篇关于炸弹人 bfs + dfs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
