도자기 가게의 황소

농부 존은 집에 장식이 좀 더 필요하다고 생각했다. 동네 도자기 가게에 들른 그는 벽난로 위 선반에 딱 어울릴 것 같은 섬세한 유리 소 장식품을 발견하고 구매하기로 한다.

소 장식품의 모양은 아래와 같은 \(N \times N\) 문자 격자로 표현된다 (\(3 \leq N \leq 8\)). '#' 문자는 장식품의 일부이고 '.' 문자는 아니다.

...............
...............
...............
#..#...........
####...........
############...
.##.#########..
....#######.##.
....##...##....
....##...##....
...............
...............
...............
...............
...............

안타깝게도 존이 계산을 하기 직전, 황소 한 마리가 가게 안을 뛰어다니며 존의 장식품뿐만 아니라 선반 위의 다른 유리 제품들까지 잔뜩 깨뜨리고 말았다! 존의 장식품은 2개의 조각으로 부서졌고, 이 조각들은 바닥에 흩어진 총 \(K\)개의 조각들 사이에 섞여 버렸다 (\(3 \leq K \leq 10\)). \(K\)개의 조각 각각은 원래 장식품과 마찬가지로 \(N \times N\) 문자 격자로 표현된다.

\(K\)개의 조각 중 어느 두 조각을 붙여야 부서진 장식품을 복원할 수 있는지 농부 존이 알아내도록 도와주자. 다행히도 장식품의 두 조각은 바닥에 떨어질 때 회전하거나 뒤집히지 않았으므로, 조각을 다시 맞추려면 조각을 가로 그리고/또는 세로로 평행 이동한 뒤 겹쳐 놓기만 하면 된다. 올바른 두 조각을 골랐다면, 이런 방식으로 원래 장식품을 정확하게 재구성할 수 있어야 하며, 원래 장식품의 각 '#'는 두 조각 중 정확히 하나에만 나타나야 한다 (즉, 두 조각을 이동시켜 겹쳤을 때 공통된 '#' 문자를 공유해서는 안 되고, 두 조각이 합쳐져서 원래 모양을 정확히 이루어야 한다).

존은 조각을 세로 그리고/또는 가로로 임의의 칸 수만큼 이동시킬 수 있지만, '#' 문자가 원래의 \(N \times N\) 격자 바깥으로 벗어날 만큼 멀리 이동시킬 수는 없다. 각 조각의 모양이 반드시 하나의 "연결된" '#' 영역으로 이루어져 있는 것은 아니다. 그렇지만 한 조각이 서로 떨어진 여러 개의 '#' 덩어리로 이루어져 있더라도, 조각 전체를 이동시키려면 덩어리들을 모두 같은 만큼 이동시켜야 한다.

문제 제공: Brian Dean

문제 제공: Brian Dean

입력의 첫째 줄에 \(N\)과 \(K\)가 주어진다. 다음 \(N\)개의 줄에 농부 존의 원래 장식품을 나타내는 문자 격자가 주어진다. 그다음 \(KN\)개의 줄에 농부 존이 바닥에서 발견한 \(K\)개의 조각을 나타내는 \(K\)개의 문자 격자가 주어진다.

농부 존의 장식품을 이루는 두 조각의 번호를 나타내는, \(1 \ldots K\) 범위의 정수 두 개를 공백으로 구분하여 한 줄에 출력한다. 해는 항상 존재하며 유일하다. 출력하는 두 수는 오름차순이어야 한다.

riseoj 작성

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