文章
35
粉丝
599
获赞
6
访问
311.6k
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()后面设置这两个判定条件?为何这么写也能到达全局的正解。
登录后发布评论
暂无评论,来抢沙发