문제
취미로 퍼즐을 즐기는 한 정올 학생이 더이상 풀 퍼즐이 없자, 새로운 퍼즐을 하나 만들었다.
이 퍼즐의 이름은 정사각형 퍼즐이다.
퍼즐 매니아 학생은 이 퍼즐을 택쌤에게 풀어보라고 했다.
택쌤은 대수롭게 않게 받아들였지만, 생각보다 너무 어려웠다.
그래서 택쌤은 퍼즐을 직접 푸는 대신, 퍼즐을 풀 수 있는 프로그램을 만드는 작업을 모의고사 문제로 내서, 여러분들이 택쌤의 일을 대신 하게 하려고 한다.
뭐 어쩔수 없다. 여러분들은 모의고사를 보는 중이니깐. 잔말말고 시원하게 풀어버리는 수밖에. 얼른 풀어서 택쌤의 코를 납작하게 만들도록 하자.
퍼즐은 N행 M열로 이루어진 2차원 보드판에서 진행된다.
보드판의 일부 칸은 사용하지 않는 칸이며, 남은 칸중에 K개의 칸은 "열쇠"를 포함하고 있다.
퍼즐 규칙은 간단하다. 보드판을 K개의 정사각형 영역으로 분할하되, 남는 영역이 없도록 해야 하고, 한 영역에 하나의 열쇠만 포함되게 하면 된다.
또한 어떤 정사각형 영역도 사용하지 않는 칸을 포함해선 안된다.
예를 들어 그림 1과 같은 경우는, 그림 2처럼 분할하는 것이 정답이다.
여기서 검정색 칸은 사용하지 않는 칸을 나타내며, 녹색은 열쇠를 나타낸다.
퍼즐의 초기상태가 주어졌을 때, 퍼즐의 해법을 출력하는 프로그램을 작성하라.
입력
첫 줄에 보드판의 행과 열 수를 나타내는 N, M이 공백을 사이에 두고 주어진다.
다음 줄부터 총 N행 M열의 보드판의 상태가 공백 없이 주어진다.
각 칸은 '$', '#' 또는 '.' 인데,
'$'는 열쇠,
'#'는 사용하지 않는 칸,
'.'는 빈 칸을 나타낸다.
모든 부분문제에서 1≤N,M≤100이다. 열쇠의 수는 1개 이상이고, 52개 이하이다.
출력
N행 M열에 걸쳐, 공백 없이, 퍼즐의 해법을 출력한다.
만약 해법이 존재하지 않는다면 No Solution을 출력하며(대소문자 구분) 그렇지 않은 경우의 출력규칙은 다음과 같다.
- 사용하지 않는 칸은 그대로 '#'을 출력한다.
- 그 외의 경우, 'A'부터 'Z'까지의 문자를, 부족하다면 'a'부터 'z'까지의 문자를 순서대로 사용하여, 같은 영역인 칸끼리는 같은 문자를 배치하여 출력한다.
- 문자 배치 순서는, 정사각형 영역의 좌상단이 i행 j열인 경우, i값이 작은 정사각형 영역부터 문자를 배치하며, 같은 경우 j값이 작은 정사각형 영역에 문자를 먼저 배치한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 9점 | N,M≤5 |
| #2 | 11점 | 열쇠의 수≤4이다. |
| #3 | 31점 | N,M≤20이고,열쇠의 수≤10이다. |
| #4 | 49점 | 주어진 조건에 더하여 아래 제약 조건이 추가로 붙고 그 외에는 아무 제약 조건이 없다. 다음 두 가지 조건 중 하나를 만족한다. - 전체 칸의 50% 이상은 사용할 수 없는 칸이다. - 정사각형 영역의 가장 윗 행을 X번째 행, 가장 왼쪽 열을 Y번째 열, 그 영역에 해당하는 열쇠의 좌표를 (xk,yk)라고 한다면 min(xk-X,yk-Y)≤3를 만족하는 정사각형 영역이 전체 정사각형 영역의 95% 이상이다. |
예제 #1
7 8
........
.$....$.
$...$...
......#$
.$....#$
...$....
$$.....$
AABBBCCC
AABBBCCC
DDBBBCCC
DDEEEE#F
GGEEEE#H
GGEEEEII
JKEEEEII
예제 #2
1 5
#$#$#
#A#B#
예제 #3
1 5
#$.$.
No Solution
로그인해야 코드를 작성할 수 있어요.