개선문 10
시간 제한1초메모리 제한1024 MB
주어진 석조 아치 단면을 가장 적은 임시 나무 블록으로 세우고, 매 단계 모든 블록이 안정되도록 블록을 놓거나 제거하는 순서를 출력합니다.
문제
황제 코스타스는 라이벌 맥스에게 거둔 승리를 기념하여 개선문을 세우려고 한다. 설계는 이미 끝났고, 이제 가장 저렴하게 개선문을 지어 줄 기술자를 찾고 있다.
개선문은 돌 블록으로 쌓은 좁은 구조물이다. 개선문은 2차원 단면으로 완전히 기술된다. 예를 들어 로마에 있는 개선문 중 하나의 단면은 다음과 같다.
########
########
########
###..###
#.#..#.#
#.#..#.#
이 단면에서 #은 블록을, .은 빈 공간을 나타낸다.
개선문이 서 있으려면 모든 블록이 안정 상태여야 한다. 블록이 안정하다는 것은 다음 조건 중 하나를 만족한다는 뜻이다.
- 땅이나 다른 안정 블록 위에 놓여 있다.
- 가로로 이어진 블록 구간에 속하고, 그 구간의 양 끝 블록이 안정하다.
아래 그림에서 블록 B는 안정 블록 C 위에 놓여 있고 C는 땅 위에 있으므로 안정하다. 블록 A는 양 끝 블록 X와 Z가 안정한 구간 XAYZ에 속하므로 안정하다.
########
########
##XAYZ##
###..###
B.#..#.#
C.#..#.#
위 그림의 개선문은 블록 A를 안정하게 놓을 방법이 없으므로 그대로는 지을 수 없다. 그래서 기술자는 임시 목조 구조물을 사용한다. 목재 블록도 돌 블록과 같은 조건으로 안정성을 판단한다.
위 그림의 개선문은 목재 블록 3개로 지을 수 있다. 핵심 단계는 다음과 같다.
..####..
###^.###
#.#^.#.#
#.#^.#.#
(^는 목재 블록을 나타낸다.)
공사는 빈 땅에서 시작하여 다음 세 가지 단계를 차례로 수행한다.
- 선택한 칸에 돌 블록을 놓는다.
- 선택한 칸에 목재 블록을 놓는다.
- 선택한 칸의 목재 블록을 제거한다.
매 순간 놓여 있는 모든 블록은 안정해야 한다. 목재 블록은 비싸므로 코스타스는 목재 블록을 가능한 적게 사들이려고 한다. 제거한 목재 블록은 다시 사용할 수 있다.
목표는 목재 블록을 가장 적게 사용해서 개선문을 짓는 것이다. 공사가 끝났을 때 돌 블록은 계획과 정확히 같은 위치에 있어야 한다. 목재 블록은 남아 있어도 된다.
입력
첫 줄에는 공백으로 구분된 네 수가 주어진다. 각각 개선문의 너비 M, 높이 N, 그리고 채점 함수를 정하는 매개변수 A와 B이다(채점 섹션 참고).
이어지는 N줄에는 개선문이 위에서 아래 순서로 주어진다. 각 줄은 #과 .으로만 이루어진 M개의 문자로 구성된다. #은 블록, .은 빈 공간이다.
출력
각 단계마다 한 줄에 블록을 추가하거나 제거할 칸의 좌표 두 수를 공백으로 구분하여 출력한다. 그 칸에 아직 블록이 없었다면 블록이 놓인다. 계획에서 그 칸이 돌 블록이면 돌 블록이, 빈 공간이면 목재 블록이 놓인다. 그 칸에 이미 목재 블록이 있었다면 그 블록은 제거된다.
제한
1 ≤ M, N ≤ 100