传送门不用标记

P1825 [USACO11OPEN] Corn Maze S

哇,我也是这么改52分直接A了,可是为什么呢??
by NanNanzi_QvQ @ 2023-05-19 18:27:37


噢,懂了,因为两个传送门可能在同一层,如果标了就没法用传送门了。
by NanNanzi_QvQ @ 2023-05-19 18:35:31


@[NanNanzi_QvQ](/user/101761) 请问在同一层是指位于bfs树的同一层吗? 同一个传送门使用过了再被使用一次会更短吗?想不出来情况。 我不标记后,多过了2个点。
by sjyh_jy @ 2023-05-28 23:00:22


我知道了,看了别人发的测试点4 从起点一个接一个传送门传送,没别的路可选,直到有一个传送门,要传过去再传回来,然后可以往上走。 就是传送门堵路这种情况。
by sjyh_jy @ 2023-05-28 23:08:17


@[sjyh_jy](/user/160570) 对,如果两个传送门在bfs的同一层,搜到第一个传送门时会标记第二个传送门,就导致第二个传送门没法用了
by NanNanzi_QvQ @ 2023-05-29 08:50:44


@[NanNanzi_QvQ](/user/101761) thx 不过还没见过同一层的情况,只见到有的传送门要传过去再传回来,所以不能标记。
by sjyh_jy @ 2023-05-29 11:31:27


@[NanNanzi_QvQ](/user/101761) 确实是不标记传送门能多对一半左右。 终于A了,我太蠢了,我用的map<char,string>存的坐标,想当然认为string[0] string[1] string[2] string[3]就是成对的坐标了,没想到有不止1位数的坐标。
by sjyh_jy @ 2023-05-29 12:07:56


|