시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 444 | 102 | 69 | 22.476% |
영선이는 카드와 그리드를 가지고 놀고 있다. 각각의 카드는 직사각형 모양이며, 색칠되어져 있다. 두 카드가 같은 색을 가지는 경우는 없으며, 크기도 카드마다 다를 수 있다.
영선이는 한 번에 카드 하나씩 그리드 위에 올려놓는다. 카드를 올려놓을 때, 그리드의 변과 평행이 되게 카드를 올려놓아야 한다. 따라서, 직사각형은 그리드의 칸을 덮게 된다. 또, 카드는 겹쳐서 놓을 수 있다. 카드가 놓이면서 어떤 카드를 완전히 가리는 경우는 없다.
카드를 다 놓은 다음, 위에서 바라본 결과가 주어진다. 이때, 카드를 놓은 순서를 구하는 프로그램을 작성하시오.
첫째 줄에 그리드의 크기 N과 M이 주어진다. (1 ≤ N, M ≤ 50)
둘째 줄부터 N개의 줄에 그리드에 놓여진 카드의 색이 주어진다. 카드의 색은 알파벳 소문자('a'-'z'), 대문자('A'-'Z'), 숫자('0'-'9') 중 하나이며, '.'는 빈 칸이다.
첫째 줄에 카드를 놓은 순서를 출력한다. 만약 가능한 순서가 여러 가지라면, 사전순으로 앞서는 것을 출력한다. 만약, 불가능한 경우에는 -1을 출력한다.
3 6 ..AA.. .CAAC. .CAAC.
CA
2 6 ..47.. ..74..
-1
5 6 bbb666 .655X5 a65AA5 a65AA5 a65555
65AXab