페그 이동 수

페그는 말 하나가 인접한 말을 뛰어넘고, 뛰어넘은 말을 제거하는 퍼즐 게임이다. 한 번 움직일 때는 위, 아래, 왼쪽, 오른쪽 중 한 방향만 사용할 수 있다.

대표적인 초기 보드는 다음과 같다.

  ooo  ooooooooooooo.oooooooooo  ooo  ooo

문자 o는 말이 있는 칸, .는 빈 칸, 공백은 보드에 포함되지 않는 위치를 뜻한다. 어떤 말의 바로 옆 칸에 다른 말이 있고 같은 방향으로 한 칸 더 떨어진 칸이 비어 있다면, 그 말은 인접한 말을 뛰어넘어 빈 칸으로 이동할 수 있다. 이때 뛰어넘은 말은 제거된다.

현재 보드 상태가 주어졌을 때 가능한 합법적인 한 번의 이동 수를 구하시오.

현재 보드 상태가 총 7줄에 걸쳐 주어진다. 보드에 포함되지 않는 모서리 위치는 공백으로 주어지고, 나머지 칸은 o 또는 .이다.

가능한 합법적인 이동 수를 출력한다.