警示后人(bfs58分)

如果你也像这个评测一样，那么以下的内容可能对你有帮助。

在常规bfs中，我们会对走过的点进行标注，但是对于这道题，常规的标注方法会出现“传送门坑人”的情况：

PLAINTEXT

@W=
##.
W#.
.#.
.#.
.#.
...

这种情况下，如果直接向右走到(2,1)，就会被传送到(1,3)，并且由于标记无法返回，只能从下方绕一大圈，输出11。此时就不如(1,3)->(1,4)->(1,3)回到(2,1)继续向右。参考代码：

if ('A' <= element.value() && element.value() <= 'Z') {  // 传送
            point t;
            for (int i = 1; i <= height; i++) {
                for (int j = 1; j <= width; j++) {
                    if (map[j][i] == element.value() && (j != element.x || i != element.y))
                        t = {j, i, element.step};
                }
            }
            element = t;
        } else {
            walked[element.x][element.y] = true;  // 标记
        }

完整ac代码

CPP

讨论操作

回复

相关推荐

警示后人(bfs58分)