文章

0

粉丝

1

获赞

37

访问

51771

头像
广度优先搜索计算每个人移动到每个位置需要去掉障碍物的最少数目,最后求和的最小值
P1308
发布于2022年2月14日 16:58
阅读数 3824

首先利用广度优先搜索计算出每个困于迷宫中的人移动到迷宫中每个位置需要去掉障碍物的最少数目,最后通过遍历迷宫中的每个位置,得到每个人移动到迷宫中每个位置需要去掉障碍物的数目的和的最小值即可。

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

const int inf = 0x3f3f3f3f;  // 定义无穷大
const int maxn = 100 + 5;

struct node {
	int x, y;
};

int n, m;

char mpt[maxn][maxn];  // 存储迷宫结构
int away[maxn][maxn][3];  // 最后一个维度代表困于迷宫中的人数,整个矩阵用于存储每个人到迷宫中每个位置需要去掉的障碍物的数目
int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};  // 移动的四个方向:向上、向下、向左、向右
node peoples[3];  // 表示困于迷宫中的人

// 使用广度优先搜索求解
void bfs(int index) {  // index 表示困于迷宫中的人的编号
	queue<node> q;  // 使用队列来维护一层层发散的优先级
	node now;
	now.x = peoples[index].x;
	now.y = peoples[index].y;
	q.push(now);
	away[now.x][now.y][index] = 0;
	while (!q.empty()) {
		now = q.front();
		q.pop();
		for (int i = 0; i < 4; ++i) {  // 上下左右四个方向
			int nx = now.x + dir[i][0];
			int ny = now.y + dir[i][1];
			// 保证移动后的位置依然位于迷宫内
			if (nx >= 1 & nx <= n & ny >= ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发