← 返回题目列表

AtCoder · icpc2013summer_day3_f

F. 普特鲍尔

中文机器翻译题面 查看原题

讨厌失败的 Ikta 最近迷上了围棋棋盘。

然而,由于我在围棋或五子棋上都无法击败我的朋友,所以我决定训练一种不太出名的游戏,称为 Phutball。

这是一场困难的比赛,所以我决定从特殊训练开始,这样我就能判断自己是否能赢得回合并完成比赛。

游戏获胜条件如下。

  • 白子不能跳到放置黑子的地方。

  • 位于围棋棋盘的中央 使用 19 \times 15 部分。

  • 想要确定胜利条件的围棋棋盘上有一颗白子和几颗黑子。

  • 目标点是指围棋棋盘的底边或其下方的区域。 (见下图。)

  • 如果你把白石带到目标点,你就赢了。

  • 要获胜,请执行以下操作:

    • 白石可以跳跃多次。

    • 跳跃可以通过跳过与白子相邻的8个方向(上、下、左、右、斜上、斜下)的任何一个黑子来完成。

    • 你不能向不与黑石相邻的方向跳跃。

    • 每次跳跃,跳过的黑子都会从棋盘顶部移走。

    • 跳跃后的白子必须位于球门点或游戏盘上。

    • 即使连续有两个或更多黑子,你也可以跳到横跨它们。

    • 白子不能跳到放置黑子的地方。 (你必须始终跳过跳跃方向上连续的黑色石头。)

图中标有圆圈的地方是可以跳到的,它们都是终点,但标有叉的地方既不是终点,也不是棋盘内,所以不能跳到那里。

你的工作是帮助伊克塔进行特殊训练,编写一个程序来确定他是否能够达到目标,并找到达到目标的最小跳跃次数。

输入

由 .OX 组成19\times 15板由 19 行给出。 每行必须包含 15 个字符,其中每个字符代表:

  • “。”代表一个空格。

  • “O”代表白石。

  • “X”代表黑石。

约束

  • 黑子数量为 20 或更少。

  • 始终只有一颗白色石头。

  • 已达到目标的状态将不会被输入。

输出

如果目标是可能的,则在一行上打印最短的移动次数。如果无法达到目标,则输出-1。

示例输入 1

...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
......O........
......X........

样本输入 1 的输出

1
  • 白石可以跳过黑石一次到达目标。

示例输入 2

...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
......O........
...............

样本输入 2 的输出

-1
  • 白石无法移动,因此他无法到达目标。

示例输入 3

...............
...............
...............
...............
...............
...............
...............
...............
...........O...
............X..
.............X.
.............X.
.............X.
...............
..............X
.........X.....
.............X.
......X....X..X
.....X.X.XX.X..

样本输入 3 的输出

6
  • 您只需尝试 6 次即可达到目标。

  • 每次跳跃的分解图像如下所示。

示例输入 4

...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
.....XX........
.....XXXO......
......X........

样本输入 4 的输出

4