驰昊代码找虫

深圳信奥算法部-吴传民

2026-02-06 10:07:08

发布于：广东

2阅读

0回复

0点赞

你这份代码主要是 BFS 写崩了，导致要么死循环、要么根本扩展不出去、要么答案永远是 -1。关键问题有这几个（前两个是致命的）：

1）你忘了 `q.pop()`：队头永远不出队 → 死循环

在 while 里你只取了 q.front()，但没有 q.pop()。

while(!q.empty()){
    int qx = q.front().x;
    int qy = q.front().y;
    // 没有 q.pop();

结果：队列第一个点一直处理不完，q 永远不空。

✅ 修复：取完后立刻 q.pop()。

2）你入队入错了：应该 push 新点，你 push 了旧点

你写的是：

q.push({qx,qy});

这会把当前点反复塞回队列，队列疯狂膨胀，永远到不了新点。

✅ 应该是：

q.push({nx, ny});

3）到达终点只 `break` 了 for，没有结束 BFS

你写：

if(nx == r && ny == c) break;

这只会跳出 for (i=0..5)，外层 while 还会继续跑，而且你也没有给终点赋值/入队（甚至可能没更新 dis）。

✅ 常见写法：

直接让 BFS 正常扩展，最后输出 dis[r][c]
或者发现终点就 return cout<<dis[nx][ny],0;（但要先更新 dis）

4）你用 `vis` 同时表示“障碍”和“访问过”，逻辑可行但要小心

你把障碍标 1：

vis[as][df] = 1;

又把访问过也标 1：

vis[nx][ny] = 1;

这本身没问题（都表示“不能再走”），但就要求你 必须正确入队新点，否则直接全乱。

5）`in_map()` 的范围莫名其妙，可能挡掉合法位置

题目坐标范围 [-200,200]，你偏移 210 后是 [10,410]。
你写的是 [5,450) 虽然“够大”，但没必要，且如果你哪天换偏移/数组大小就容易炸。

建议直接用 0<=x<421 这种严格范围。

你这份代码的最小改动版（能 AC）

尽量保留你结构，只改必须改的：

#include<bits/stdc++.h>
using namespace std;

int n,r,c,dis[810][810];
int vis[810][810];
int xp[] = {1,0,-1,1,-1,0};
int yp[] = {1,1,1,0,0,-1};

bool in_map(int x,int y){ return x>=0 && y>=0 && x<421 && y<421; }

struct e{ int x,y; };
queue<e> q;

int main(){
    memset(dis,-1,sizeof(dis));
    cin>>n>>r>>c;
    r += 210; c += 210;

    for(int i=1;i<=n;i++){
        int as,df;
        cin>>as>>df;
        as += 210; df += 210;
        vis[as][df] = 1;          // 障碍
    }

    dis[210][210] = 0;
    vis[210][210] = 1;            // 起点视作已访问
    q.push({210,210});

    while(!q.empty()){
        auto cur = q.front(); q.pop();
        int qx = cur.x, qy = cur.y;

        for(int i=0;i<6;i++){
            int nx = qx + xp[i];
            int ny = qy + yp[i];

            if(!in_map(nx,ny)) continue;
            if(vis[nx][ny]) continue;

            dis[nx][ny] = dis[qx][qy] + 1;
            vis[nx][ny] = 1;
            q.push({nx,ny});
        }
    }

    cout << dis[r][c];
    return 0;
}