友谦代码找虫

深圳信奥算法部-吴传民

2026-02-06 10:33:50

发布于：广东

3阅读

0回复

0点赞

这份代码的核心问题是：障碍和坐标偏移处理全错了，导致你 BFS 基本是在“错误的地图”上跑，很多时候会直接穿过障碍或者把空气当障碍。

下面是致命点（按影响从大到小）：

1）障碍没有加偏移就标记了（必 WA）

你读入障碍 (u,v) 后，目标和起点都加了 +210，但你标障碍却用了原坐标：

vis[u][v]=1;

正确应该标在偏移后的格子：

vis[u+210][v+210] = 1;

否则障碍位置整体错位，BFS 当然跑不对。

2）你写了个没用的语句：`dis[u+210][v+210];`

这一句啥也没干：

dis[u+210][v+210];

你大概率想写的是把障碍标出来（比如 vis[...] = 1 或 dis[...] = -2），但现在它就是“访问了一下数组”，编译能过但毫无意义。

3）`cmp()` 的边界范围不规范（可能漏点/越界风险）

你写：

if (x<9||y<9||x>411||y>411) return false;

这范围是拍脑袋的，不对应题目 [-200,200] 偏移后 [10,410] 的精确范围。
建议直接写清楚：

if (x<0 || y<0 || x>=421 || y>=421) return false;

或者如果你想只允许 [10,410]：

if (x<10 || y<10 || x>410 || y>410) return false;

4）`cmp()` 用 `vis` 同时表示“障碍/访问过”是可以的，但你现在标障碍错位导致全乱

你在 BFS 里：

if (vis[x][y]) return false;

这意味着 vis 既表示“障碍”，也表示“已经访问过”。这没问题，前提是你障碍标对位置。但你现在没加偏移就标了，所以 cmp 会莫名其妙禁止一些格子、放过真正的障碍格子。

最小修改版（保留你的结构）

只改关键地方就能正常：

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

int dx[]={1,0,-1,1,-1,0};
int dy[]={1,1,1,0,0,-1};
int n,r,c;
int dis[500][500];
bool vis[500][500];

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

bool cmp(int x,int y){
    if (x<10||y<10||x>410||y>410) return false; // [-200,200] + 210
    if (vis[x][y]) return false;                // 障碍 or 已访问
    return true;
}

void bfs(int x,int y){
    q.push({x,y});
    vis[x][y]=1;
    dis[x][y]=0;

    while(!q.empty()){
        auto t=q.front(); q.pop();
        int nx=t.x, ny=t.y;

        if (nx==r && ny==c){
            cout<<dis[nx][ny];
            return;
        }

        for(int i=0;i<6;i++){
            int nxt=nx+dx[i], nyt=ny+dy[i];
            if (cmp(nxt,nyt)){
                vis[nxt][nyt]=1;
                dis[nxt][nyt]=dis[nx][ny]+1;
                q.push({nxt,nyt});
            }
        }
    }
    cout<<-1;
}

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

    for(int i=1;i<=n;i++){
        int u,v; cin>>u>>v;
        vis[u+210][v+210]=1; // ✅障碍要偏移
    }

    bfs(210,210);
    return 0;
}