도자기 가게의 황소

농부 존은 집에 장식이 더 필요하다고 생각했다. 동네 도자기 가게에 들른 존은 벽난로 위 선반에 딱 어울릴 것이라 확신하며, 섬세한 유리 소 조각상을 하나 사기로 한다.

소 조각상의 모양은 아래와 같은 \(N \times M\) 문자 격자로 표현된다(\(3 \leq N, M \leq 500\)). 소문자 알파벳 문자는 각각 조각상의 일부이며(서로 다른 색을 나타낸다), '.' 문자는 조각상이 아니다.

...............
...............
x..x...........
xxxx...........
xxxxaaaaaaa...
.xx.aaaaaaaaa..
....aaaaaaa.aa.
....ll...ll....
....vv...vv....
...............

불행히도 존이 계산을 하기 직전, 황소 한 마리가 가게 안을 내달리며 존의 조각상은 물론 선반 위의 다른 유리 제품들까지 여럿 깨뜨리고 말았다! 존의 조각상은 3개의 조각으로 깨졌고, 이 조각들은 바닥에 널린 총 \(K\)개의 조각(\(4 \leq K \leq 100\)) 사이에 순식간에 뒤섞여 버렸다. \(K\)개의 조각 각각은 원래 조각상과 마찬가지로 문자 격자로 표현된다.

바닥에 있는 \(K\)개의 조각 중에서, 3개를 골라 붙였을 때 깨진 조각상을 복원할 수 있는 조각 3개의 조합이 몇 가지인지 구해 존을 도와주자.

바닥의 조각들은 상하 또는 좌우로 뒤집혔거나, 90도의 배수만큼 회전되었을 수 있다. 따라서 원래 격자와 조각들을 나타내는 \(K\)개의 격자가 주어질 때, 평행 이동, 뒤집기, 90도의 배수 회전을 허용하여 원래 그림을 만들 수 있는 조각 3개의 조합을 찾아야 한다. 세 조각을 겹쳐 놓았을 때 정확히 원래 그림이 되어야 하며, 원래 그림의 색칠된 각 칸은 정확히 하나의 조각에만 나타나야 한다.

문제 출제: 브라이언 딘(Brian Dean)

문제 출제: 브라이언 딘(Brian Dean)

첫째 줄에 정수 \(K\)가 주어진다. 그 뒤로 \(K + 1\)개의 조각 설명이 이어진다. 첫 번째 설명은 원래의 유리 소를 나타내고, 이어지는 \(K\)개의 설명은 깨진 조각들을 나타낸다.

각 설명은 두 정수 \(R\)과 \(C\)(\(1 \le R, C \le 100\))가 있는 줄로 시작한다. 이어지는 \(R\)개의 줄에는 각 칸의 색을 나타내는 \(C\)개의 소문자 알파벳 문자가 주어진다. 각 조각은 상하좌우로 연결되어 있으며, 비어 있지 않은 칸을 적어도 하나 가진다.

조각 \(i\), \(j\), \(k\)를 배치하여 원래의 유리 소를 만들 수 있는 삼중쌍 \(i, j, k\)(\(i < j < k\))의 개수를 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2015-2016 > US Open > Platinum