シムロード (SimRoad) 3

JOI 社はシムロードというシミュレーションゲームを販売している．このゲームでは，プレイヤーは舞 台となる国の統治者となり，その国を繁栄させるべく様々な操作を行う．

舞台となる国は原始時代である．国には集落が点在しているのだが，この国は多くが背の高い草で覆わ れており，その状態では集落間を容易に移動することはできない．プレイヤーであるあなたの最初のミッ ションは住人が集落間を容易に移動できるように草刈をすることである．

国の状態は東西 W マス，南北 H マスで区切られた 3 種類の状態で表されるマスからなる．‘w’ はそのマ スが草で覆われていることを示し，‘.’ はそのマスが更地である (草で覆われていない) ことを示し，‘@’ は そのマスには集落があることを示す．

住人は東西南北の隣り合った 4 方向のマスのうち集落または更地であるマスへは自由に移動することが できるが，草で覆われているマスは移動できない．そこで，住人が集落間を容易に移動できるように草で 覆われているマスの草を刈り取り更地にすることにより，どの集落からも全ての集落に移動できるように 草を刈らなければならない．

草で覆われているマスの草を刈るとそのマスを更地にすることができるが，草刈をするには住人を働か せる必要があり，1 マスの草を刈るためには 1 ドルのお金がかかる．後々の繁栄のことを考えると使うお 金は少ない方が良い．

当然，草の刈り取り方は多数存在することがある．与えられた国の状態から，出来る限り草を刈り取る マスが少ない方法で草を刈り，その後の国の状態を生成しなさい．

基本アルゴリズム (BASIC ALGORITHM): y' を H が偶数であれば H/2 とし，H が奇数であれば (H + 1)/2 とする．まず北から y' 行目のマスのう ち草で覆われたマスを全て刈り取り，次に全ての集落について南北方向に北から y' マス目との間にある草 で覆われたマスがあれば全て刈り取る．

入力ファイルは以 下のような形式で与えられる．

• 1 行目には整数 W と H が空白を区切りとして書かれている．
• 続く H 行には各行 W 文字の文字列が書かれており，国の状態を表す．これらの行の y 行目の x 文字 目には，‘w’ または ‘.’ または ‘@’ の文字が書かれており，北から y マス目，西から x マス目のマス の状態を表す．

出力データはファイルで提出せよ．

• 草刈をした後の国の状態を書け．出力は H 行からなり，各行は W 文字の文字列である．これらの行 の y 行目の x 文字目には，北から y マス目，西から x マス目のマスの状態を表す ‘w’ または ‘.’ また は ‘@’ の文字を書け．

• 1 ≤ W ≤ 100 国の東西方向のマスの数
• 1 ≤ H ≤ 100 国の南北方向のマスの数

この出力例の場合は，7 マスの草が覆われていたマスの草を刈り取り更地にしているため，7 ドルのお金 がかかっている．この出力例を提出した場合，もしあなたより小さな金額で作ることのできる国の状態の 出力を提出した人がいなければ 20 点を得るが，Em が 6 ドルであれば 12.9 点を得ることとなる．

上記の入力例に対する基本アルゴリズムの出力は次のようになり，10 マスの草が覆われていたマスの草 を刈り取り更地にしているため，10 ドルのお金がかかる．

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