종이 자르기
시간 제한2초메모리 제한128 MB
회전 없이 평행이동만으로 다섯 조각을 L x L 정사각형에 정확히 채울 수 있는지 판별하고, 가능하면 사전순으로 가장 작은 배치를, 불가능하면 gg를 출력하는 문제입니다.
문제
송유진은 L x L 크기의 정사각형 모눈종이를 가지고 있다. 이 모눈종이는 가로 L칸, 세로 L칸으로 나뉘며, 각 칸은 1 x 1 크기의 정사각형이다.
차영훈은 이 모눈종이를 격자선을 따라 잘라 정확히 5개의 조각으로 만들었다. 이제 송유진은 주어진 다섯 조각을 회전하지 않고 L x L 정사각형 안에 다시 배치해야 한다.
입력
첫째 줄에 정사각형 한 변의 길이 L이 주어진다. (3 <= L <= 10)
그다음에는 첫 번째 조각부터 다섯 번째 조각까지의 정보가 차례대로 주어진다.
각 조각의 정보는 다음 형식이다.
- 첫째 줄에 조각의 세로 크기 N과 가로 크기 M이 주어진다. (1 <= N, M <= L)
- 이어지는 N개의 줄에는 조각의 모양이 주어진다. 각 줄은 길이 M이며
#과.으로만 이루어져 있다. #은 조각이 차지하는 칸,.은 빈칸을 뜻한다.- 조각 정보의 첫 행, 마지막 행, 첫 열, 마지막 열에는 각각 적어도 하나의
#이 있다.
출력
다섯 조각을 회전하지 않고 L x L 정사각형에 겹치지 않게 배치하여 모든 칸을 채울 수 있다면, 각 칸을 차지한 조각의 번호를 출력한다. 조각 번호는 입력으로 주어진 순서대로 1부터 5까지이다.
출력은 L개의 줄로 이루어지며, 각 줄은 해당 행의 L개 칸에 적힌 번호를 나타낸다.
가능한 배치가 여러 가지라면, 모든 행을 위에서부터 차례대로 이어 붙여 만든 문자열이 사전순으로 가장 앞서는 배치를 출력한다.
조건을 만족하는 배치가 없으면 gg를 출력한다.