c++ - 追溯先前遵循的路径

Question

我有一个 1000 x 1000 的网格，其中一个人 Q 从起点 A 到终点 B。当 Q 从 A 出发时，他随机行走直到他到达 B。随机行走的意思是对于 Q 当前所在的任何位置 (i,j)，Q 可以以相等的速度移动到 (i+1,j) , (i-1,j) , (i,j+1), (i,j-1)可能性。如果 Q 以这种方式到达 B ，他会得到一个存放在 B 的宝藏，现在他想原路返回他从 A 到 B 所走的完全相同的路径，只是倒退。

有没有一种方法可以在 C++ 中实现这一点，而无需将路径显式存储在 vector 中？

Answer 1

你也许可以这样做:

• 存储随机数种子
• 为定向移动获取 1 到 4 之间的随机数
• 存储移动计数，从 0 开始(已经在目的地)
• 对于您没有到达目的地的每一步，增加计数。
• 每次从您的随机数中减去一个固定数。

到达目的地后，反向遍历移动计数种子，从计数到 0，然后采取相反的移动。

重点是将移动计数和种子联系起来。假设随机种子是一个形式函数，给定相同的输入，您应该总是得到相同的输出。您可以存储初始时间，固定时间步，然后让您的种子成为每个时间步的当前时间，但我们的想法是让您的种子与计数相关。

使用此方法，您应该能够仅使用开始时间和到达目标所需的刻度数来提取路径。此外，还有一个额外的好处:您还可以存储到达目的地所花费的时间，并根据该时间状态获取其他变量。