도자기 가게의 황소 (브론즈)

시간 제한2초메모리 제한512 MB

요약
회전 없이 평행 이동한 두 조각이 겹치지 않고 원래 격자를 정확히 복원하는 쌍을 찾습니다.
난이도

쉬움10점 중 3점

유형
완전 탐색, 시뮬레이션
정답자
아직 제출이 없습니다

문제

농부 존은 집을 조금 더 꾸미기로 했다. 동네 도자기 가게에 들른 존은 벽난로 위 선반에 딱 맞을 유리 소 장식을 발견하고 사기로 마음먹는다.

소 장식의 모양은 N×NN \times N 크기의 문자 격자로 주어진다(3≤N≤83 \le N \le 8). '#'은 장식의 일부인 칸이고, '.'은 장식이 아닌 칸이다. N=8N = 8인 예는 다음과 같다.

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

존이 값을 치르기 직전에 황소 한 마리가 가게를 헤집고 지나가면서 이 장식은 물론 선반 위 유리 제품도 여럿 깨뜨린다. 존의 장식은 조각 두 개로 깨졌고, 바닥에 흩어진 조각 KK개 사이에 섞여 버렸다(3≤K≤103 \le K \le 10). 조각 KK개는 각각 원래 장식과 같은 형식의 N×NN \times N 문자 격자로 주어진다.

조각 KK개 가운데 존이 다시 붙여야 할 두 조각을 찾아라. 조각은 떨어질 때 회전하지도 뒤집히지도 않았으므로, 존은 두 조각을 가로세로로 평행 이동한 뒤 겹치기만 하면 된다. 두 조각이 정말 존의 장식에서 나온 것이라면, 원래 장식의 '#' 하나하나가 두 조각 중 정확히 하나에만 들어가도록 평행 이동할 수 있다. 즉 겹쳐 놓은 두 조각은 '#'을 공유하지 않고, 합치면 원래 모양과 정확히 같아진다.

조각은 가로로도 세로로도 원하는 만큼 평행 이동할 수 있지만, '#'이 하나라도 N×NN \times N 격자 밖으로 나가도록 옮길 수는 없다. 한 조각의 '#'이 한 덩어리로 이어져 있지 않을 수도 있다. 조각이 떨어진 덩어리 여러 개로 이루어진 경우, 그 조각을 옮길 때는 모든 덩어리를 같은 양만큼 옮긴다.

입력

첫째 줄에 NN과 KK가 공백으로 구분되어 주어진다. 다음 NN개 줄에 원래 장식의 모양을 나타내는 문자 격자가 주어진다. 이어지는 K×NK \times N개 줄에 존이 바닥에서 찾은 조각 KK개의 격자가 차례로 주어진다.

출력

존의 장식을 이루는 두 조각의 번호를 공백으로 구분해 한 줄에 출력한다. 번호는 11 이상 KK 이하이고, 작은 번호를 먼저 쓴다. 답은 항상 존재하며 유일하다.

예제1

  1. 예제 1

    입력
    4 3
    ####
    #..#
    #.##
    ....
    .#..
    .#..
    ##..
    ....
    ####
    ##..
    #..#
    ####
    ....
    .###
    .#..
    .#..
    
    예상 출력
    1 3