페그 이동 수
면접 대비시간 제한1초메모리 제한128 MB
7행으로 주어진 십자형 페그 보드에서 현재 가능한 한 번의 점프 이동 수를 세는 문제입니다.
문제
페그는 말 하나가 인접한 말을 뛰어넘고, 뛰어넘은 말을 제거하는 퍼즐 게임이다. 한 번 움직일 때는 위, 아래, 왼쪽, 오른쪽 중 한 방향만 사용할 수 있다.
대표적인 초기 보드는 다음과 같다.
ooo
ooo
ooooooo
ooo.ooo
ooooooo
ooo
ooo
문자 o는 말이 있는 칸, .는 빈 칸, 공백은 보드에 포함되지 않는 위치를 뜻한다. 어떤 말의 바로 옆 칸에 다른 말이 있고 같은 방향으로 한 칸 더 떨어진 칸이 비어 있다면, 그 말은 인접한 말을 뛰어넘어 빈 칸으로 이동할 수 있다. 이때 뛰어넘은 말은 제거된다.
현재 보드 상태가 주어졌을 때 가능한 합법적인 한 번의 이동 수를 구하시오.
입력
현재 보드 상태가 총 7줄에 걸쳐 주어진다. 보드에 포함되지 않는 모서리 위치는 공백으로 주어지고, 나머지 칸은 o 또는 .이다.
출력
가능한 합법적인 이동 수를 출력한다.