3

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

我想知道如何将其简化为一些基本的知名算法。如果游戏中没有“时间”，我会建立一个安全位置图并找到一条通往青蛙目的地的路径。但是，我不能使用这种方法。

如何将“ Frogger”简化为众所周知的问题？

4

2 回答 2

1

假设汽车和青蛙小心翼翼地移动，一次一个“正方形”，让我们用 V 表示青蛙垂直移动（穿过马路）的次数和青蛙水平移动的次数（沿着车道） ) by H. 如果你说 5 条车道，1-5，青蛙可以在 T=X + 2*V + H 形式的时刻在车道 X 上。到目前为止，一切都很好。

由于每个车道上的汽车在时刻 T 的状态是确定性的，我们可以在未来一段合理的时间内生成整条道路的状态：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) 形式的虚构道路状态) 并寻找一种状态，在该状态中，您有一条通往另一侧的开放直线，因此消除了时间分量。

实际上，你是在暴力破解它，但假设有合理数量的车道和允许的移动，你没有理由不这样做。

于 2012-08-25T10:17:51.593 回答
1

我猜想这样的事情会以简单的形式工作。（假设这是关于如何运行游戏，而不是如何解决它）

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

类似的东西？

于 2012-08-25T10:19:00.703 回答