개선문 1
시간 제한1초메모리 제한1024 MB
아치 단면을 안정적으로 쌓는 순서를 찾고, 나무 블록을 가장 적게 써서 모든 설치와 제거 단계를 출력합니다.
문제
황제 코스타스는 라이벌 맥스에게 거둔 승리를 기념하기 위해 개선문을 세우려고 합니다. 이미 설계는 끝났고, 이제 가장 저렴하게 지어 줄 기술자를 찾고 있습니다.
개선문은 돌 블록으로 만든 좁은 구조물입니다. 구조물은 이차원 단면도로 완전하게 나타낼 수 있습니다. 예를 들어 로마에 있는 개선문 가운데 하나의 단면도는 다음과 같습니다.
########
########
########
###..###
#.#..#.#
#.#..#.#
이 단면도에서 #은 블록을, .은 빈 칸을 나타냅니다.
아치가 서 있으려면 모든 블록이 안정 상태여야 합니다. 블록은 다음 조건 중 하나를 만족하면 안정 상태입니다.
- 땅 위나 다른 안정 블록 위에 놓여 있다
- 바깥쪽 블록이 안정 상태인 가로 방향 블록 구간에 속한다
예를 들어 다음 그림을 봅시다.
########
########
##XAYZ##
###..###
B.#..#.#
C.#..#.#
블록 B는 안정 블록 C 위에 놓여 있으므로 안정 상태입니다. 블록 C는 땅 위에 놓여 있으므로 안정 상태입니다. 블록 A는 구간 XAYZ에 속하고, 그 바깥쪽 블록 X와 Z가 안정 상태이므로 안정 상태입니다.
아치는 블록을 하나씩 올려서 세웁니다. 세우는 과정의 어느 순간에도 모든 블록이 안정 상태여야 합니다. 그래서 임시 구조물 없이는 세울 수 없는 아치도 있습니다. 위 그림의 아치는 블록 A를 안정 상태로 놓을 방법이 없어서 그대로는 세울 수 없습니다. 따라서 기술자는 나무 블록으로 만든 임시 구조물을 사용합니다. 돌 블록과 나무 블록은 안정성을 판단할 때 똑같이 취급합니다.
위 아치는 나무 블록 세 개로 세울 수 있습니다. 핵심 단계는 다음과 같습니다.
..####..
###^.###
#.#^.#.#
#.#^.#.#
(^은 나무 블록을 나타냅니다.)
작업은 빈 땅에서 시작하여 다음 단계를 차례로 수행합니다. 단계는 세 종류입니다.
- 선택한 칸에 돌 블록을 놓는다
- 선택한 칸에 나무 블록을 놓는다
- 선택한 칸에서 나무 블록을 치운다
어느 순간에든 세워진 블록은 모두 안정 상태여야 합니다. 나무 블록은 비싸므로 코스타스는 가능한 한 적게 사려고 합니다. 치운 나무 블록은 다시 쓸 수 있습니다.
여러분의 과제는 나무 블록을 가장 적게 사용해 아치를 세우는 것입니다. 작업이 끝났을 때 돌 블록은 계획에 적힌 위치에 정확히 있어야 합니다. 나무 블록은 남아 있어도 괜찮습니다.
입력
첫 줄에는 공백으로 구분된 네 개의 수가 주어집니다. 아치의 너비 M, 아치의 높이 N, 그리고 점수 함수를 설명하는 매개변수 A와 B입니다(채점 항목 참조).
이어지는 N개의 줄은 위에서 아래 순서로 아치를 나타냅니다. 각 줄은 M개의 기호로 이루어지며, #은 블록, .은 빈 칸을 뜻합니다.
출력
작업의 전 과정을 출력합니다. 각 단계마다 블록을 놓거나 치울 칸의 좌표를 공백으로 구분한 두 개의 수로 한 줄에 출력합니다.
그 칸에 블록이 없다면 블록을 놓습니다. 계획에서 그 위치가 돌 블록이면 돌 블록을, 빈 칸이면 나무 블록을 놓습니다. 그 칸에 이미 나무 블록이 있다면 치웁니다.
제한
1 ≤ M, N ≤ 100