文章

35

粉丝

599

获赞

35

访问

336.8k

头像
讨论: ac代码bfs中的疑惑
P1308
发布于2020年5月7日 11:03
阅读数 10.1k

void bfs(int index)
{
	queue<node> q;
	node now, next;
	now.x = p[index].x;
	now.y = p[index].y;
	q.push(now);
	vis[now.x][now.y][index] = 0;
	while (!q.empty()){
		now = q.front();
		q.pop();
		for (int i = 0; i < 4; i++){
			next = now;
			next.x += dir[i][0];
			next.y += dir[i][1];
			if (next.x<1 || next.x>n || next.y<1 || next.y>m) continue;
			int tmp = vis[now.x][now.y][index];
			if (mpt[next.x][next.y] == '#')tmp++;//遇到一个障碍物,那么此人到达这个点需要消掉的障碍物加1
			if (tmp < vis[next.x][next.y][index]){
				//判断是否可以让需要消掉的障碍物更小
				vis[next.x][next.y][index] = tmp;
				q.push(next);
			}
		}
	}
}

以上ac代码核心段一直在累加遇到的障碍物数量,退出条件应该是到达边界n,m时队列空。而题目要求的退出条件是到达另外两个点,例如w和f,为什么不在q.pop()后面设置这两个判定条件?为何这么写也能到达全局的正解。

登录查看完整内容


登录后发布评论

2 条评论
litery
2026年2月19日 17:35

因为不是统计步数,要找到最少障碍的办法就要全部探索完,找到A--B,B--C,C--A的最小障碍数,其中两个最小值相加得到结果

赞(0)

litery : 回复 litery: 不能删评,纠正一下,是找到一个汇聚点,对三个人到汇聚点的最小障碍数相加

2026年2月19日 19:52
回复给: