Phutball
시간 제한2초메모리 제한512 MB
19×15 판에 흰 돌 하나와 검은 돌 20개 이하가 주어질 때, 흰 돌이 목표 지점에 도달하는 최소 점프 횟수를 구하거나 불가능하면 -1을 출력한다.
문제
負けず嫌いのイクタ君は、最近囲碁盤を使って遊ぶゲームに熱中している。
しかし、囲碁も五目並べも友人に全く勝てないので、あまり有名でない Phutball というゲームの特訓をすることにした。
このゲームは難しいゲームなので、手始めに自分のターンに勝って終局できるかを判定できるように特訓することにした。
ゲームの勝利条件は以下のようなものである。
- 白石は黒石の置かれている場所にジャンプすることは出来ない。
-
碁盤の中央のの部分を用いる。
-
勝利条件を判定したい碁盤は白石が1つと黒石がいくつか置かれた状態で与えられる。
-
ゴール地点というのは碁盤の下端か、その下側を指す。（下図を参照せよ。）
-
ゴール地点に白石を運べば勝利する。
-
勝利するために以下のようなことを行う。
-
白石は1回以上ジャンプを行うことができる。
-
ジャンプは白石に隣接する8方向（上下左右と斜め上、斜め下）の黒石のどれかを飛び越えることで行える。
-
黒石が隣接していない方向へジャンプすることは出来ない。
-
飛び越えられた黒石は、1回のジャンプごとに碁盤の上から取り除かれる。
-
ジャンプしたあとの白石はゴール地点かゲーム盤の上に存在しなければいけない。
-
黒石が2個以上連続していても、ちょうどそれをまたぐようにジャンプできる。
-
白石は黒石の置かれている場所にジャンプすることは出来ない。(ジャンプする方向に連続している黒石は必ず飛び越えなくてはならない。)
-
図の丸印がついている場所へはジャンプすることが可能であり、全てゴール地点であるが、バツ印の場所はゴール地点でもなく、碁盤の内側でもないので、ジャンプすることは出来ない。
あなたの仕事はイクタ君の特訓を手助けするために、ゴールできるかどうかの判定と、ゴールするための最小のジャンプ回数を求めるプログラムを書いてあげる事である。
입력
.OXで構成されたの盤面が19行で与えられる。 各行は必ず15文字からなり、各文字は次を表す。
-
"."は空白を表す。
-
"O"は白石を表す。
-
"X"は黒石を表す。
출력
ゴール可能なら最短の手数を1行に出力せよ。ゴールすることが不可能な場合は-1を出力せよ。
제한
-
黒石の数が20以下。
-
白石は必ず1つだけ存在する。
-
すでにゴールした状態が入力されることはない。