暑期题单新知识——前驱节点の记录 与 其作用

[王皓宇 (小鸽子)]

题目：

其实本来弄对了，不想讲的，但考虑到有很多题目要求（输出行走路径），所以也记录一下

是这个路径吗？其实并不是，简单来说，从（0,0）开始，到（2,0）（第3列第1个，10），路径为RRRDDLLL（只有8个，是因为9是个岔路，所以对于8来说，到10和9的步数是一样的，而步数是从1开始而不是0）

回到题目

暴搜O(2的1e6次方)，直接考虑每个格子走不走

dfs 写不了一点，因为并不了解最短路径的长度

bfs 可简单了，已经加过的地点不用再加，因为路径短的一定在前面，O(nm)秒了

……

……

……

孩子，BFS 的梦该醒了

你猜为啥？

还是什么函数调用,花了1e7条指令？

绝对不是！！！

时间复杂度不够优秀？最大O(1e6)，CCF的评测机都行

是！但不完全是！

为什么，先看下面

就这两段，要知道，字符串拼接的时间复杂度可是非常惨烈的O(len)

所以时间复杂度最大比O(nm)大不少

怎么办？？？

因为最短路仅仅只要一条，所以在路线外的字符串拼接的操作都是冗余的，所以……

我们直接罢工，不拼接了，把每一次要拼接的字符串记录下来，也就是记录合并的前一个节点，这，就是（前驱结点）

如果最终对答案没影响，那么你还拼个der，时间多到没出用吗？

最终仅要最短路的所有点的移动方式拼接，直接将nm次减了不少（最多好像还是n² / 2 多 几 ，最短路走全图，最少应该是 n + m - 1）

看这个↓↓↓↓↓↓

具体实现（部分）

有问题可以提出，后面有时间我会改

[冯俊骁 (仔仔熊)]

等等，这个不应该发在 经验分享区 吗