負けず嫌いのイクタ君は、最近囲碁盤を使って遊ぶゲームに熱中している。 しかし、囲碁も五目並べも友人に全く勝てないので、あまり有名でない Phutball というゲームの特訓をすることにした。
このゲームは難しいゲームなので、手始めに自分のターンに勝って終局できるかを判定できるように特訓することにした。
ゲームの勝利条件は以下のようなものである。
- 白石は黒石の置かれている場所にジャンプすることは出来ない。
- 碁盤の中央の 19 × 15 の部分を用いる。
- 勝利条件を判定したい碁盤は白石が1つと黒石がいくつか置かれた状態で与えられる。
- ゴール地点というのは碁盤の下端か、その下側を指す。（下図を参照せよ。）
- ゴール地点に白石を運べば勝利する。
- 勝利するために以下のようなことを行う。
- 白石は1回以上ジャンプを行うことができる。
- ジャンプは白石に隣接する8方向（上下左右と斜め上、斜め下）の黒石のどれかを飛び越えることで行える。
- 黒石が隣接していない方向へジャンプすることは出来ない。
- 飛び越えられた黒石は、1回のジャンプごとに碁盤の上から取り除かれる。
- ジャンプしたあとの白石はゴール地点かゲーム盤の上に存在しなければいけない。
- 黒石が2個以上連続していても、ちょうどそれをまたぐようにジャンプできる。
- 白石は黒石の置かれている場所にジャンプすることは出来ない。(ジャンプする方向に連続している黒石は必ず飛び越えなくてはならない。)
図の丸印がついている場所へはジャンプすることが可能であり、全てゴール地点であるが、バツ印の場所はゴール地点でもなく、碁盤の内側でもないので、ジャンプすることは出来ない。
あなたの仕事はイクタ君の特訓を手助けするために、ゴールできるかどうかの判定と、ゴールするための最小のジャンプ回数を求めるプログラムを書いてあげる事である。
Input
.OXで構成された19 × 15の盤面が19行で与えられる。 各行は必ず15文字からなり、各文字は次を表す。
- "."は空白を表す。
- "O"は白石を表す。
- "X"は黒石を表す。
Constraints
- 黒石の数が20以下。
- 白石は必ず1つだけ存在する。
- すでにゴールした状態が入力されることはない。
Output
ゴール可能なら最短の手数を1行に出力せよ。ゴールすることが不可能な場合は-1を出力せよ。
Sample Input 1
............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ......O........ ......X........
Output for the Sample Input 1
1
- 白石は黒石を1回ジャンプしてゴールすることができる。
Sample Input 2
............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ......O........ ...............
Output for the Sample Input 2
-1
- 白石は移動できないのでゴールできない。
Sample Input 3
............... ............... ............... ............... ............... ............... ............... ............... ...........O... ............X.. .............X. .............X. .............X. ............... ..............X .........X..... .............X. ......X....X..X .....X.X.XX.X..
Output for the Sample Input 3
6
- ちょうど6回でゴールできる。
- ジャンプ毎に分解した画像を以下に示す。
Sample Input 4
............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... ............... .....XX........ .....XXXO...... ......X........
Output for the Sample Input 4
4