실행 시간 제한 | 메모리 제한 |
---|---|
5 초 | 512 MB |
도시의 작은 예술가, 승훈은 자신의 집을 더 아름답게 꾸미고 싶어했습니다. 현지 도자기 상점을 방문하면서 그는 완벽하게 벽난로 위의 선반에 어울리는 섬세한 유리 동물 조각상을 구입하기로 결정했습니다.
이 동물 조각상의 모양은 아래와 같이 문자 격자로 설명됩니다 (). 여기서 소문자 문자는 각각 조각상의 일부입니다 (다른 색상을 나타냄) 그리고 '.' 문자는 포함되지 않습니다.
...............
...............
x..x...........
xxxx...........
xxxxaaaaaaa...
.xx.aaaaaaaaa..
....aaaaaaa.aa.
....ll...ll....
....vv...vv....
...............
불행히도 승훈이 구입을 하려는 바로 직전에, 한 마리의 짐승이 상점을 달려들어 승훈의 조각상은 물론 선반 위의 다른 유리 물체들을 모두 깨뜨렸습니다! 승훈의 조각상은 3개의 조각으로 깨지고, 빠르게 바닥에 떨어진 개의 조각 중에서 찾을 수 없게 되었습니다. 각 조각은 원래의 조각상처럼 문자 격자로 설명됩니다.
승훈의 깨진 조각상을 복원하기 위해 3개의 조각을 붙여서 다시 조립할 수 있는 조각 세트가 몇 개인지 알려주세요.
바닥에 떨어진 조각들은 수직이나 수평으로 뒤집히거나, 90도의 배수로 회전될 수 있습니다. 따라서 원래의 격자와 격자를 주어진 조각을 기술하면, 3개의 조각을 원래의 그림을 형성하도록 결합하여 원래 그림을 정확하게 형성해야 합니다. 각 색상이 원래 그림에 정확하게 나타나야 하며, 조각 중 하나에만 표시됩니다.
첫 번째 줄에는 단일 정수 가 포함됩니다. 그 다음은 개의 조각 설명이 이어집니다. 첫 번째 설명은 원래의 유리 동물을 설명하고, 다음 설명은 깨진 조각들을 나타냅니다.
각 설명은 과 를 포함하는 줄로 시작합니다 (). 다음 줄에는 각 셀의 색상을 설명하는 소문자 알파벳 문자가 포함됩니다. 각 조각은 수평/수직으로 연결되어 있으며, 적어도 하나의 비어 있지 않은 셀이 있습니다.
원래의 유리 동물을 형성하기 위해 조각 , , 및 를 배열할 수 있는 조합의 수를 출력하세요.
5 5 5 aaaaa ..a.. bbabb ..a.. aaaaa 3 5 ..abb ..a.. aaaaa 5 2 a. a. aa a. a. 1 2 bb 1 5 bbabb 2 5 aaaaa ..a..
3
조각 , , 를 조합하면 원래의 그림을 완벽하게 형성할 수 있습니다.
이 문제는 테스트 케이스 당 시간 제한이 6초(자바와 파이썬 제출에 대해서는 두 배)입니다.
출처: USACO 2016 US Open Contest, Platinum Problem 2. Bull in a China Shop