POJ 3009 冰壶 2.0

在MM-21星球上，今年奥运会结束后，冰壶运动开始流行。但规则和我们的有些不同。该游戏在标有方形网格的冰游戏板上进行。他们只使用一块石头。 p

在MM-21星球上，今年奥运会结束后，冰壶运动开始流行。但规则和我们的有些不同。该游戏在标有方形网格的冰游戏板上进行。他们只使用一块石头。游戏的目的 就是用最少的步数将石头从起点引到终点。

图。附图说明图1示出了游戏板的示例。有些方格可能被方块占据。有两个特殊的方格，即起点和目标，没有被方块占据。 （这两个方块是不同的。）一旦石头开始移动，它就会继续移动 直到碰到一个方块。为了将石头带到目标处，您可能需要通过将石头撞到块上来阻止石头，然后再次投掷。

图 1：棋盘示例（S：开始，G：目标）

石头的运动遵循以下规则：

• 开始时，石头静止在起始广场上。
• 石头的移动仅限于 x 和 y 方向。禁止对角移动。
• 当石头静止不动时，你可以通过扔它来使其移动。你可以将它扔向任何方向，除非它立即被阻挡（图2(a)）。
• 一旦扔出，石头就会一直向同一方向移动，直到发生以下其中一种情况：
  • 石头击中方块（图2(b)、(c)）。
    • 石头停在它击中的方块旁边的广场上。
    • 方块消失了。
  • 石头从棋盘中出来。
    • 游戏以失败告终。
  • 石头到达球门方格。
    • 石头停在那里，游戏成功结束。
• 一场游戏中扔石头的次数不能超过 10 次。如果 10 步内石头没有到达目标，游戏就会失败。

图2：石头运动

根据规则，我们想知道一开始的棋子能否到达目标，如果可以，需要最少移动多少步。

如图 1 所示的初始配置，需要 4 步才能将石头从起点带到目标。路线如图3(a)所示。请注意，当石头到达目标时，棋盘配置发生了变化，如图 3(b) 所示。

图 3：图 D-1 的解决方案和最终的电路板配置