Problem:


負けず嫌いのイクタ君は、最近囲碁盤を使って遊ぶゲームに熱中している。
しかし、囲碁も五目並べも友人に全く勝てないので、あまり有名でない Phutball というゲームの特訓をすることにした。

このゲームは難しいゲームなので、手始めに自分のターンに勝って終局できるかを判定できるように特訓することにした。

ゲームの勝利条件は以下のようなものである。

 白石は黒石の置かれている場所にジャンプすることは出来ない。

 碁盤の中央の 19 &times; 15 の部分を用いる。

 勝利条件を判定したい碁盤は白石が1つと黒石がいくつか置かれた状態で与えられる。

 ゴール地点というのは碁盤の下端か、その下側を指す。（下図を参照せよ。）

 ゴール地点に白石を運べば勝利する。

 勝利するために以下のようなことを行う。

 白石は1回以上ジャンプを行うことができる。

 ジャンプは白石に隣接する8方向（上下左右と斜め上、斜め下）の黒石のどれかを飛び越えることで行える。

 黒石が隣接していない方向へジャンプすることは出来ない。

 飛び越えられた黒石は、1回のジャンプごとに碁盤の上から取り除かれる。

 ジャンプしたあとの白石はゴール地点かゲーム盤の上に存在しなければいけない。

 黒石が2個以上連続していても、ちょうどそれをまたぐようにジャンプできる。

 白石は黒石の置かれている場所にジャンプすることは出来ない。(ジャンプする方向に連続している黒石は必ず飛び越えなくてはならない。)

図の丸印がついている場所へはジャンプすることが可能であり、全てゴール地点であるが、バツ印の場所はゴール地点でもなく、碁盤の内側でもないので、ジャンプすることは出来ない。

あなたの仕事はイクタ君の特訓を手助けするために、ゴールできるかどうかの判定と、ゴールするための最小のジャンプ回数を求めるプログラムを書いてあげる事である。

Input

.OXで構成された19 &times; 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



Sample input:
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
...............
......O........
......X........


Sample output:
1

Submission status: Wrong Answer

Solution code:
INF = 100
mp = [list("#" * 17)] + [list("#" + input() + "#") for _ in range(19)] + [list("G" * 17)]
for y in range(1, 20):
  for x in range(1, 16):
    if mp[y][x] == "O":
      sx, sy = x, y
      mp[y][x] = "."

vec = ((1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1))
ans = INF
def search(x, y, score):
  global ans
  if score >= ans:return
  for dx, dy in vec:
    nx, ny = x, y
    use = []
    while mp[ny + dy][nx + dx] == "X":
      nx += dx
      ny += dy
      use.append((nx, ny))
    if mp[ny + dy][nx + dx] == "G":
      ans = score + 1
      return
    if mp[ny + dy][nx + dx] == "#":
      continue
    if mp[ny + dy][nx + dx] == "." and use:
      for ux, uy in use:
        mp[uy][ux] = "."
      search(nx + dx, ny + dy, score + 1)
      for ux, uy in use:
        mp[uy][ux] = "X"

search(sx, sy, 0)
if ans == INF:print(-1)
else:print(ans)

Submission status: Wrong Answer

Solution code:
INF = 100
mp = [list("#" * 17)] + [list("#" + input() + "#") for _ in range(19)] + [list("G" * 17)]
for y in range(1, 20):
  for x in range(1, 16):
    if mp[y][x] == "O":
      sx, sy = x, y
      mp[y][x] = "."
for x in range(17):
  if mp[19][x] != "X":mp[19][x] = "G"

vec = ((1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1))
ans = INF
def search(x, y, score):
  global ans
  if score >= ans:return
  for dx, dy in vec:
    nx, ny = x, y
    use = []
    while mp[ny + dy][nx + dx] == "X":
      nx += dx
      ny += dy
      use.append((nx, ny))
    if not use:continue
    if mp[ny + dy][nx + dx] == "G":
      ans = score + 1
      return
    if mp[ny + dy][nx + dx] == "#":
      continue
    if mp[ny + dy][nx + dx] == ".":
      for ux, uy in use:
        mp[uy][ux] = "."
      search(nx + dx, ny + dy, score + 1)
      for ux, uy in use:
        mp[uy][ux] = "X"

search(sx, sy, 0)
if ans == INF:print(-1)
else:print(ans)

Submission status: Time Limit Exceeded

Solution code:
INF = 100
mp = [list("#" * 17)] + [list("#" + input() + "#") for _ in range(19)] + [list("G" * 17)]
for y in range(1, 20):
  for x in range(1, 16):
    if mp[y][x] == "O":
      sx, sy = x, y
      mp[y][x] = "."
for x in range(1, 16):
  if mp[19][x] != "X":mp[19][x] = "G"

vec = ((1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1))
ans = INF
def search(x, y, score):
  global ans
  if score >= ans:return
  for dx, dy in vec:
    nx, ny = x, y
    use = []
    while mp[ny + dy][nx + dx] == "X":
      nx += dx
      ny += dy
      use.append((nx, ny))
    if not use:continue
    if mp[ny + dy][nx + dx] == "G":
      ans = score + 1
      return
    if mp[ny + dy][nx + dx] == "#":
      continue
    if mp[ny + dy][nx + dx] == ".":
      for ux, uy in use:
        mp[uy][ux] = "." if uy < 19 else "G"
      search(nx + dx, ny + dy, score + 1)
      for ux, uy in use:
        mp[uy][ux] = "X"

search(sx, sy, 0)
if ans == INF:print(-1)
else:print(ans)

Submission status: Accepted

Solution code:
def main():
    N = 20; M = 15
    MP = [[-1]*M for i in range(N)]
    L = 0
    for i in range(N-1):
        s = input()
        for j in range(M):
            c = s[j]
            if c == 'O':
                sx = j; sy = i
            elif c == 'X':
                MP[i][j] = L
                L += 1

    dd = ((-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1))

    INF = 30
    D = {}
    def dfs(state, x, y):
        key = (state, x, y)
        if key in D:
            return D[key]
        if y >= N-2:
            return 0
        r = INF
        for dx, dy in dd:
            nx = x + dx; ny = y + dy
            if not 0 <= nx < M or not 0 <= ny < N:
                continue
            k = MP[ny][nx]
            if k == -1 or state & (1 << k) == 0:
                continue
            n_state = state ^ (1 << k)
            nx += dx; ny += dy
            while 0 <= nx < M and 0 <= ny < N:
                k = MP[ny][nx]
                if k == -1 or state & (1 << k) == 0:
                    break
                n_state ^= (1 << k)
                nx += dx; ny += dy
            else:
                if (nx == -1 or nx == M) and ny == N-1:
                    return 1
                continue
            r = min(r, dfs(n_state, nx, ny) + 1)
        D[key] = r
        return D[key]
    r = dfs(2**L-1, sx, sy)
    print(r if r < INF else -1)
main()