“青蛙”游戏的算法

Question

这是个面试问题。设计了一个播放“青蛙”的算法。也就是说，你指挥一只青蛙，它必须穿过一条繁忙的道路。青蛙可以向前/向后和左右移动，汽车只能向左移动，青蛙和汽车一次只能移动一个位置。

我想知道怎样才能把它简化成一些基本的著名算法。如果游戏中没有“时间”，我会建立一个安全位置图，并找到一条通往青蛙目的地的路径。然而，我不能使用这种方法。

如何将“青蛙”简化成一个众所周知的问题？

Answer 1

假设汽车和青蛙一次移动一个“正方形”，让我们表示青蛙垂直移动(横过马路)的次数是V，而青蛙水平移动(沿着一条车道)的次数是H。如果你有5条车道，1-5条，那么青蛙可以在X号车道上出现T=X + 2*V + H。到目前为止，非常好。

由于每条车道上的车辆在一段时间内的状态是确定的，所以我们可以在未来合理的时间内生成整个道路的状态: L(1，T)L(2，T)...L(5，T)。我建议你生成形式L(1,1 + 2*V + H)L(2,2 + 2*V + H)...L(5,5 + 2*V + H)的虚拟道路状态，并寻找一种与另一侧有一条开放直线的状态，从而消除时间分量。

实际上，你是在蛮横地强迫它，但没有理由不这样做，假设有合理的车道和允许的移动。

Answer 2

我猜像这样的东西会以一种简单的形式起作用。(假设这是一个如何运行游戏，而不是如何解决它)

1) build array to store all tiles on map (each segment of road / water / log)
2) build list to store car / log locations
3) Set up a timer
4) on timer tick, update array of locations with full/empty tiles for each car / log in list (2)
5) check whether the current locaiton of the frog is in the same location as a log / car
6) repeat 4/5 while frog can move

像那样吗？