시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 0 0 0 0.000%

문제

농부 John은 자기 집을 좀 더 꾸밀 필요가 있다고 생각했습니다. 중국 물품 가게에 갔다가 그는 섬세한 유리 소 장식품을 발견했고, 벽난로 선반에 놓으면 딱 적당할 것 같아서 그만 구매하기로 했습니다.

소 장식품의 모양은 아래에 나와있는 것처럼 (3 <= N, M <= 500) 인 N x M 형태의 문자 배열로 적혀있고, 소문자 영어가 (각각이 다른 색인) 장식품의 각 부분을 나타냅니다. '.' 기호는 아무것도 없는 빈 공간입니다.

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

안타깝게도 농부 John이 이 장식품을 구매하기 바로 직전에 이놈의 황소가 가게를 가로질러 날아가더니, 농부 John이 사기로 했던 장식물 말고도 선반에 있던 다른 여러 장식물까지 박살내버렸네요! 농부 John의 조각상은 3조각으로 나뉘었는데, 결국 바닥에 떨어져있는 (4 <= K <= 100)인 모두 K개의 조각들 사이에 섞여서 사라져버렸네요. 각 조각은 위의 소 조각상처럼 문자 배열로 적혀있습니다.

농부 John이 (바닥에 떨어진 K조각 중) 다시 이어붙여 소로 만들 수 있는 3조각의 조합을 얼마나 만들 수 있는지 파악하도록 도와주세요.

바닥에 떨어진 조각은 가로로 혹은 세로로 뒤집어져 있거나, 90도씩 회전되어 있을 수 있습니다. 그래서 K개의 주어진 조각의 배열에서, 원래 모양대로 만들 수 있는 3개의 조각의 조합을 찾기 위해, 조각을 이동하거나, 뒤집거나, 90도씩 회전할 수 있습니다. 그렇게 조각들을 놓았을 때, 놓여진 3조각이 각각의 원래 조각과 색상까지 완전히 동일하게 일치해야 합니다.

입력

입력의 첫 번째 줄은 단일 정수 K가 주어집니다. 다음 줄부터는 K + 1개의 조각을 설명합니다. 첫 번째 조각은 원래 소 장식품의 모양이 기술되고, 다음 줄 부터는 K개의 조각들의 모양을 설명합니다.

각각의 조각 설명은 두 정수 R, C (1 <= R, C <= 100) 이 적혀있는 줄로 시작합니다. 뒤따라 나오는 R개의 줄에는 각 칸의 색을 표현하는 한 줄에 C개씩의 소문자 알파벳이 나옵니다. 각 조각은 수직 / 수평으로 이어져있고 적어도 하나의 비어있는 칸이 있습니다.

출력

원래 조각을 만들 수 있는 조각 i, j, k (i < j < k)의 조합의 갯수를 출력하세요.

예제 입력

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

힌트

세 해결방법은 조각 (0, 1, 2), (0, 2, 4), (1, 3, 4) 를 사용합니다.

출처

Olympiad > USA Computing Olympiad > 2015-2016 Season > US Open 2016 Contest > Platinum 2번

  • 문제의 오타를 찾은 사람: ntopia
  • 문제를 번역한 사람: sftblw