文章

35

粉丝

599

获赞

6

访问

311.6k

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

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()后面设置这两个判定条件?为何这么写也能到达全局的正解。

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发