컴퓨터를 위한 직소 퍼즐
시간 제한2초메모리 제한512 MB
주어진 정사각형 조각 아홉 개를 3x3 격자에 자유롭게 회전해 배치할 때, 맞닿는 모든 변이 대문자와 소문자 짝으로 일치하는 해의 수를 센다.
문제
일반적인 직소 퍼즐은 시각적 단서로 푼다. 퍼즐이 완성되었을 때 보이는 그림과 조각의 다양한 무늬를 보고 맞춘다. 이런 직소 퍼즐은 패턴 인식과 상상력이 필요하므로 사람이 풀기에 알맞다.
반면에 아래에서 설명하는 "직소 퍼즐"은 단순한 컴퓨터에 딱 알맞은 물건일지도 모른다.
그림 1과 같이 퍼즐은 정사각형 조각 아홉 개로 이루어지고, 각 조각의 네 변에는 다음 여덟 가지 기호 중 하나가 붙는다.
"R", "G", "B", "W", "r", "g", "b", 그리고 "w".
그림 1: 퍼즐의 조각 아홉 개
완성된 퍼즐에서 조각 아홉 개는 3 x 3 격자에 놓이고, 서로 마주 보는 변 12쌍은 각각 다음 네 가지 기호 조합 중 하나로 표시되어야 한다.
"R"과 "r", "G"와 "g", "B"와 "b", 그리고 "W"와 "w".
예를 들어 "R"이 붙은 변은 "r"이 붙은 변하고만 마주 볼 수 있다. 그림 2는 완성된 퍼즐의 한 예이다. 그림에서 이 제약을 받는 변은 기호에 음영을 넣어 나타냈다. 플레이어는 조각을 자유롭게 옮기고 회전할 수 있지만 뒤집을 수는 없다. 조각의 뒷면에는 기호가 없다!
그림 2: 완성된 퍼즐의 예
각 조각은 조각에 있는 네 기호를 위쪽 변부터 시작해 오른쪽 변, 아래쪽 변, 왼쪽 변 순서로 나열한 문자열로 나타낸다. 예를 들어 gwgW는 그림 1에서 가장 왼쪽 조각을 나타낸다. 같은 조각은 90도, 180도, 270도 회전할 수 있으므로 wgWg, gWgw, Wgwg로도 나타낼 수 있다.
여러분의 임무는 해의 개수를 세는 프로그램을 만드는 것이다. 이 수는 4의 배수일 수밖에 없다. 그림 3과 같이 해를 90도, 180도, 270도 회전해서 만든 배치도 해이기 때문이다.
그림 3: 완성된 퍼즐의 자명한 네 가지 변형
"회전 동일"이라는 용어를 정의한다. 서로 다른 두 조각이 한 조각을 90도, 180도, 270도 회전했을 때 같아지면 두 조각은 회전 동일하다. 예를 들어 WgWr과 WrWg는 회전 동일하다.
또 "회전 대칭"이라는 용어를 정의한다. 어떤 조각이 자기 자신과 회전 동일하면 그 조각은 회전 대칭이다. 예를 들어 조각 gWgW는 회전 대칭이다.
주어진 퍼즐은 다음 세 조건을 만족한다.
- 퍼즐 안에 완전히 같은 조각 쌍이 없다.
- 퍼즐 안에 회전 동일한 조각 쌍이 없다.
- 퍼즐 안에 회전 대칭인 조각이 없다.
입력
입력은 여러 퍼즐로 이루어진다.
N
Puzzle1
Puzzle2
. . .
PuzzleN
N은 퍼즐의 수이다. 각 Puzzlei는 퍼즐 하나를 나타내며, 퍼즐의 조각 아홉 개를 네 글자씩 표현한 것을 공백 문자 하나로 구분해 한 줄에 44글자로 준다. 예를 들어 다음 줄은 그림 1의 퍼즐을 나타낸다.
gwgW RBbW GWrb GRRb BWGr Rbgw rGbR gBrg GRwb
출력
각 Puzzlei의 해의 개수를 한 줄에 하나씩 출력한다.