시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 29 | 3 | 2 | 22.222% |
농부 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) 를 사용합니다.