SP3999 FROGGER - FROGGER

《Frogger》是一款由SEGA在1981年推出的经典街机游戏。游戏的目标是引导青蛙安全穿越多条车道而不被汽车撞到。你将面对一个有 $n$ 条车道的公路，每条车道有 $m$ 个位置，这些位置可能是空的，也可能有汽车。公路两侧是青蛙可以自由移动的路缘石。在车道上，青蛙只能移动到没有被汽车占据的位置。公路设计使得每条车道上的车行驶方向交替，最靠近青蛙起点的第一条车道上的汽车向右行驶。汽车始终保持在自己的车道内，每次前进一步。当汽车到达车道末端时，会从另一端重新进入，确保车流不断。游戏中，所有汽车会同时移动一步，而青蛙可以选择移动或静止：每次可以向左、向右、向上或向下移动一步（包括在车道之间或路缘石和相邻车道之间移动）。与汽车不同，青蛙不能“穿越”到车道或路缘石的另一端。青蛙与汽车同步移动，所以青蛙只能移动到下个回合没有汽车的位置。如果青蛙和汽车同时处于同一个位置，青蛙会被撞死。青蛙可以越过同一车道接近它的汽车。你的任务是编写一个程序，计算青蛙从起点到终点所需的最少回合数，或判断在规定的最大回合数内无法完成。

首先是一行，表示需要帮助青蛙的场景数量。接下来，每个场景包括如下几行： - 第一行：一个正整数 $x \leq 10^5$，代表青蛙可以使用的最大回合数。 - 第二行：两个整数 $n$ 和 $m$，$1 \leq n \leq 20$，$1 \leq m \leq 50$，表示车道的数量和每条车道的长度。 - 接下来的 $n + 2$ 行表示具体的道路情况： - 第一行：表示终点路缘，由`O`和一个`G`组成，`G`为青蛙目标位置。 - 中间的 $n$ 行：每行是一个长度为 $m$ 的字符串，`X` 表示汽车，`O` 表示空位。 - 最后一行：表示起点路缘，由`O`和一个`F`组成，`F`为青蛙起始位置。

对于每个场景，输出一行，表示青蛙从起点到达终点所需的最少回合数。如果在最大允许回合数内无法达到终点，则输出相应提示信息。 **本翻译由 AI 自动生成**