你这版代码问题更多,而且有几个是 必炸/必 WA 的那种。我按“哪里错 → 为什么 → 怎么改”给你点出来(不绕弯)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1)BFS 里用错变量:你一直用入参 X,Y 在扩展
在 bfs() 里:
这里的 x,y 是函数参数(起点),永远不变。
你应该用当前出队点 now.x, now.y:
否则队列里塞再多点,你每次都从起点往外扩 6 个方向,完全不对。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2)边界判断写反 + 逻辑也错:会越界访问 DIS[NX][NY]
你写:
问题:
* !inMap(nx,ny) 的情况下你还去访问 dis[nx][ny],先越界再判断(RE/UB)。
* 逻辑也错:正确逻辑应该是 “出界 OR 障碍 OR 已访问 就跳过”。
正确写法(顺序非常重要):
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3)DIS 的初始化和含义冲突:你把所有点设成 -1,但 BFS 判断用的也是 -1
你初始化:
但 BFS 又写:
* -1 既像“未访问”,又被你当成“可走”,逻辑乱套。
* dis[nx][ny] += ... 也是错的(见下一条)。
建议:
* dis = -1 表示未访问
* 起点 dis[sx][sy]=0
* 扩展时:dis[nx][ny] = dis[now.x][now.y] + 1
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4)距离更新公式错:你用了 +=
你写:
如果 dis[nx][ny] 初始是 -1,那就会变成 (-1) + dist + 1 = dist,碰巧第一次还“像是对的”,但一旦重复入队就全乱了,而且 BFS 本就不该重复入队。
应该是赋值:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
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 来阻止走障碍点
你读了障碍:
但 BFS 里根本没判断 mp[nx][ny],所以会直接穿过去。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7)INMAP() 的边界瞎写,会把很多合法点排掉
你写:
这会把 05、415 之类全禁掉,非常奇怪。
题目坐标范围是 [-200,200],偏移 210 后就是 [10,410]。你想留边界缓冲可以,但要按范围来,最好直接开 SZ=2*SHIFT+1=421:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
给你一份“就按你这个数组 BFS”能 AC 的最小改法(核心修正)
我尽量保留你的写法,但把关键 bug 全修掉: