昨天的 ABC246E 是一道双端队列 01-BFS,而 01-BFS 的每一个状态应该是第一次被拓展时就得到了最优的答案,所以我在判断是否能拓展时这样写:
if (dis[nx][ny][i] == inf && 1 <= nx && nx <= n && 1 <= ny && ny <= n && ch[nx][ny] != '#')
结果这样写总是 WAx9,于是我在赛后看了题解,题解的写法是这样的:
if (dis[nx][ny][i] > (新的距离) && 1 <= nx && nx <= n && 1 <= ny && ny <= n && ch[nx][ny] != '#')
我按照题解的写法试了一下,就 AC 了。
所以,我的写法为什么有问题?