泽佳代码找虫

深圳信奥算法部-吴传民

2026-02-06 10:05:00

发布于：广东

2阅读

0回复

0点赞

你这版代码问题更多，而且有几个是 必炸/必 WA 的那种。我按“哪里错 → 为什么 → 怎么改”给你点出来（不绕弯）。

1）BFS 里用错变量：你一直用入参 `x,y` 在扩展

在 bfs() 里：

node now = q.front();
...
ll nx = x + dx[i], ny = y + dy[i];

这里的 x,y 是函数参数（起点），永远不变。
你应该用当前出队点 now.x, now.y：

ll nx = now.x + dx[i], ny = now.y + dy[i];

否则队列里塞再多点，你每次都从起点往外扩 6 个方向，完全不对。

2）边界判断写反 + 逻辑也错：会越界访问 `dis[nx][ny]`

你写：

if(!inMap(nx, ny) && dis[nx][ny] != -1) continue;

问题：

!inMap(nx,ny) 的情况下你还去访问 dis[nx][ny]，先越界再判断（RE/UB）。
逻辑也错：正确逻辑应该是 “出界 OR 障碍 OR 已访问就跳过”。

正确写法（顺序非常重要）：

if(!inMap(nx, ny)) continue;
if(mp[nx][ny]) continue;          // 障碍
if(dis[nx][ny] != -1) continue;   // 已访问

3）`dis` 的初始化和含义冲突：你把所有点设成 -1，但 BFS 判断用的也是 -1

你初始化：

dis[i][j] = -1;

但 BFS 又写：

if(... && dis[nx][ny] != -1) continue;
else { dis[nx][ny] += dis[now.x][now.y] + 1; }

-1 既像“未访问”，又被你当成“可走”，逻辑乱套。
dis[nx][ny] += ... 也是错的（见下一条）。

建议：

dis = -1 表示未访问
起点 dis[sx][sy]=0
扩展时：dis[nx][ny] = dis[now.x][now.y] + 1

4）距离更新公式错：你用了 `+=`

你写：

dis[nx][ny] += dis[now.x][now.y] + 1;

如果 dis[nx][ny] 初始是 -1，那就会变成 (-1) + dist + 1 = dist，碰巧第一次还“像是对的”，但一旦重复入队就全乱了，而且 BFS 本就不该重复入队。

应该是赋值：

dis[nx][ny] = dis[now.x][now.y] + 1;

5）起点、终点坐标完全没对齐

题目起点是 (0,0)，你 bfs(1,1)。

同时你把障碍坐标加了 210 偏移，但 r,c 没加偏移，输出 dis[r][c] 也没加偏移，整个坐标系统不一致。

正确做法：统一偏移，比如 SHIFT=210：

起点：sx=SHIFT, sy=SHIFT
障碍：(x+SHIFT, y+SHIFT)
终点：(r+SHIFT, c+SHIFT)
输出：dis[tx][ty]

6）你完全没用 `mp` 来阻止走障碍点

你读了障碍：

mp[v][u] = 1;

但 BFS 里根本没判断 mp[nx][ny]，所以会直接穿过去。

7）`inMap()` 的边界瞎写，会把很多合法点排掉

你写：

return x < 415 && x > 5 && y > 5 && y < 415;

这会把 0_5、415 之类全禁掉，非常奇怪。
题目坐标范围是 [-200,200]，偏移 210 后就是 [10,410]。你想留边界缓冲可以，但要按范围来，最好直接开 SZ=2*SHIFT+1=421：

return 0 <= x && x < SZ && 0 <= y && y < SZ;

给你一份“就按你这个数组 BFS”能 AC 的最小改法（核心修正）

我尽量保留你的写法，但把关键 bug 全修掉：

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

const int SHIFT = 210;
const int SZ = 2 * SHIFT + 1; // 421

ll n, r, c;
ll dis[SZ][SZ];
bool mp[SZ][SZ];

ll dx[6] = {1, 0, -1, 1, -1, 0};
ll dy[6] = {1, 1, 1, 0, 0, -1};

struct node{ int x, y; };

inline bool inMap(int x, int y){
    return 0 <= x && x < SZ && 0 <= y && y < SZ;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for(int i=0;i<SZ;i++)
        for(int j=0;j<SZ;j++)
            dis[i][j] = -1, mp[i][j] = 0;

    cin >> n >> r >> c;

    for(int i = 0; i < n; i++){
        int x, y;
        cin >> x >> y;                 // (xi, yi)
        mp[x + SHIFT][y + SHIFT] = 1;
    }

    int sx = SHIFT, sy = SHIFT;
    int tx = r + SHIFT, ty = c + SHIFT;

    queue<node> q;
    dis[sx][sy] = 0;
    q.push({sx, sy});

    while(!q.empty()){
        auto now = q.front(); q.pop();
        if(now.x == tx && now.y == ty) break;

        for(int k=0;k<6;k++){
            int nx = now.x + dx[k], ny = now.y + dy[k];
            if(!inMap(nx, ny)) continue;
            if(mp[nx][ny]) continue;           // 障碍
            if(dis[nx][ny] != -1) continue;    // 已访问
            dis[nx][ny] = dis[now.x][now.y] + 1;
            q.push({nx, ny});
        }
    }

    cout << dis[tx][ty];
    return 0;
}