페그 퍼즐

시간 제한1초메모리 제한128 MB

요약

빈 칸, 말, 막힌 칸으로 이루어진 5x5 페그 솔리테어 판이 주어질 때, 가로 또는 세로 점프를 어떤 순서로 해도 남길 수 있는 말의 최소 개수를 구한다.

난이도: 보통10점 중 7점
유형: DFS, 백트래킹, 완전 탐색, 비트 연산
정답자: 아직 제출이 없습니다

문제

페그 게임은 여러 가지 모양의 판에서 즐길 수 있지만, 목표는 언제나 같다. 판 위에 남는 페그(말)의 개수를 최대한 적게 만드는 것이다. 이를 위해 다음과 같은 이동을 반복한다. 하나의 페그가 바로 옆에 붙어 있는 다른 페그를 뛰어넘어, 그 반대편의 빈 칸에 착지한다. 뛰어넘어진 페그는 즉시 판에서 제거된다.

이동은 가로 또는 세로 방향으로만 할 수 있다. 즉, 페그 $A$ 의 바로 옆 칸에 페그 $B$ 가 있고 $B$ 의 한 칸 너머가 비어 있으면, $A$ 는 $B$ 를 뛰어넘어 그 빈 칸으로 이동하고 $B$ 는 제거된다.

페그 판의 초기 배치가 주어질 때, 최적의 이동 순서를 따랐을 때 판에 남게 되는 페그의 개수를 구하여라.

판은 다음 기호로 표현한다.

. : 페그가 없는 빈 칸
o : 페그가 놓인 칸
# : 사용할 수 없는 칸 (페그를 놓을 수도, 지나갈 수도 없음)

아래는 표준적인 5×5 십자 모양 판의 예시다. 그림 A는 빈 판, 그림 B는 페그 5개가 놓인 판, 그림 C는 그림 B에서 최적의 이동을 마친 결과다. 그림 C에는 페그가 1개만 남아 있으며, 이는 어떤 게임에서도 얻을 수 있는 최선의 결과다. 이러한 최적의 이동 순서가 유일하지는 않을 수 있다.

그림 A (빈 판):

#...#
.....
.....
.....
#...#

그림 B (페그 5개):

#.o.#
..o..
oo.o.
.....
#...#

그림 C (최적 이동 후):

#...#
.....
...o.
.....
#...#

주어지는 판이 모두 같은 모양은 아니다. 모든 판은 5×5 크기이며, 페그가 적어도 1개, 빈 칸이 적어도 1개, 사용할 수 없는 칸이 적어도 4개 있다. 하지만 그 배치는 위 예시와 크게 다를 수 있다.

입력

첫째 줄에 분석할 판의 개수 $n$ 이 주어진다.

이어지는 $5n$ 개의 줄에 판들이 주어진다. 각 판은 5개의 줄로 이루어지며, 각 줄은 위에서 설명한 기호(., o, #) 5개로 이루어진 문자열이다.

출력

각 판에 대해, 최적의 이동을 모두 마친 뒤 판에 남는 페그의 개수를 $Y$ 라 할 때, 다음 문장을 한 줄에 출력한다.

The best case ends with Y pegs.

여기서 Y는 실제로 남은 페그의 개수로 바꾸어 출력한다.

예제1

예제 1

입력

3
#.o.#
..o..
oo.o.
.....
#...#
#...#
o.o.o
....o
...o.
#o..#
#..##
.o..#
ooo.o
.o.o.
#..o#

예상 출력

The best case ends with 1 pegs.
The best case ends with 4 pegs.
The best case ends with 2 pegs.