심로드 (SimRoad) 3

JOI 사는 시뮬레이션 게임 심로드(SimRoad)를 판매한다. 이 게임에서 플레이어는 무대가 되는 나라의 통치자가 되어 그 나라를 번영시키기 위해 여러 조작을 한다.

무대가 되는 나라는 원시 시대이다. 나라에는 마을이 곳곳에 흩어져 있는데, 나라의 많은 부분이 키 큰 풀로 덮여 있어 그 상태로는 마을 사이를 쉽게 이동할 수 없다. 플레이어인 당신의 첫 임무는 주민이 마을 사이를 쉽게 이동할 수 있도록 풀을 베는 것이다.

나라의 상태는 동서 방향 $W$칸, 남북 방향 $H$칸으로 나뉜 칸들로 나타나며, 각 칸은 세 가지 상태 중 하나이다. 'w'는 그 칸이 풀로 덮여 있음을, '.'은 그 칸이 빈 땅(풀로 덮이지 않음)임을, '@'는 그 칸에 마을이 있음을 나타낸다.

주민은 동서남북으로 인접한 4방향 칸 중 마을 또는 빈 땅인 칸으로 자유롭게 이동할 수 있지만, 풀로 덮인 칸으로는 이동할 수 없다. 따라서 주민이 마을 사이를 쉽게 이동할 수 있도록 풀로 덮인 칸의 풀을 베어 빈 땅으로 만들어, 어떤 마을에서도 모든 마을로 이동할 수 있게 해야 한다.

풀로 덮인 칸의 풀을 베면 그 칸을 빈 땅으로 만들 수 있지만, 풀을 베려면 주민을 일하게 해야 하고 1칸의 풀을 베는 데 1달러가 든다. 이후의 번영을 생각하면 쓰는 돈은 적을수록 좋다.

당연히 풀을 베는 방법은 여러 가지일 수 있다. 주어진 나라의 상태에서 가능한 한 풀을 베는 칸이 적은 방법으로 풀을 베고, 그 후의 나라 상태를 생성하시오.

기본 알고리즘 (BASIC ALGORITHM): $y'$를 $H$가 짝수이면 $H/2$, $H$가 홀수이면 $(H + 1)/2$라 하자. 먼저 북쪽에서 $y'$번째 행의 칸 중 풀로 덮인 칸을 모두 베고, 다음으로 모든 마을에 대해 남북 방향으로 북쪽에서 $y'$번째 칸과의 사이에 있는 풀로 덮인 칸이 있으면 모두 벤다.

입력 파일은 다음과 같은 형식으로 주어진다.

• 첫 줄에는 정수 $W$와 $H$가 공백으로 구분되어 쓰여 있다.
• 이어지는 $H$줄에는 각 줄 $W$글자의 문자열이 쓰여 있으며, 나라의 상태를 나타낸다. 이 줄들 중 $y$번째 줄의 $x$번째 문자에는 'w' 또는 '.' 또는 '@'가 쓰여 있으며, 북쪽에서 $y$번째, 서쪽에서 $x$번째 칸의 상태를 나타낸다.

출력 데이터는 파일로 제출하시오.

• 풀을 벤 후의 나라 상태를 쓰시오. 출력은 $H$줄로 이루어지며, 각 줄은 $W$글자의 문자열이다. 이 줄들 중 $y$번째 줄의 $x$번째 문자에는 북쪽에서 $y$번째, 서쪽에서 $x$번째 칸의 상태를 나타내는 'w' 또는 '.' 또는 '@'를 쓰시오.

• $1 \le W \le 100$: 나라의 동서 방향 칸 수
• $1 \le H \le 100$: 나라의 남북 방향 칸 수

이 출력 예의 경우 풀로 덮여 있던 7칸의 풀을 베어 빈 땅으로 만들었으므로 7달러가 든다. 이 출력 예를 제출했을 때, 당신보다 적은 금액으로 만들 수 있는 나라 상태의 출력을 제출한 사람이 없으면 20점을 받지만, Em이 6달러이면 12.9점을 받게 된다.

예제 입력에 대한 기본 알고리즘의 출력은 다음과 같고, 풀로 덮여 있던 10칸의 풀을 베어 빈 땅으로 만들었으므로 10달러가 든다.

w@ww@w@
w.ww.w.
....@..
@w.w.ww
ww@.@w.