SimRoad(シムロード) - joi2010-day3

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

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

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

課題(TASK)

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

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

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

基本アルゴリズム(BASIC ALGORITHM)

y’をHが偶数であればH/2とし, Hが奇数であれば(H+1)/2とする. まず北からy’行目のマスのうち草で覆われたマスを全て刈り取り, 次に全ての集落について南北方向に北からy’マス目との間にある草で覆われたマスがあれば全て刈り取る．

制限(CONSTRAINTS)

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

入力(INPUT)

入力データは全部で5つあり, ファイル名はsimroad-in"k".txt (k = 1, 2, 3, 4, 5) である. 入力ファイルは以下のような形式で与えられる.

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

出力(OUTPUT)

出力データはファイルで提出せよ. 出力ファイルのファイル名はsimroad-out"k".txt (k = 1, 2, 3, 4, 5) である. simroad-out"k".txt にはsimroad-in"k".txt に対応した以下の形式のファイルを提出せよ.

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

採点基準(GRADING)

得点は，あなたが出力した国の状態に依存する. あなたの各々のデータに対する得点は次のように決められる. 課題の仕様に合致しない出力である場合, 得点は0 点となる. 仕様に合致している場合は, 次のように得点は計算される. E[y]をあなたの出力した国の状態にするためにかかる金額とし, E[b]を基本アルゴリズムが生成する国の状態にするためにかかる金額とし, E[m] を競技参加者が提出した出力の国の状態にするためにかかる金額の最小値とする. この場合のあなたの得点は

E[y] = E[b] ならば0
E[y] < E[b] ならば20×(1/E[y]-1/E[b])÷(1/E[m]-1/E[b])

の小数第2位を四捨五入した値である.

入出力例(EXAMPLE)

入力例(Sample Input)
`7 5 w@ww@w@ w.wwwww wwww@ww wwwwww ww.@w.`

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

基本アルゴリズムによる出力(Output by the basic algorithm)
`w@ww@w@ w.ww.w. …... @w.w.ww ww.@w.`

以下は, 上記の入力例に対する出力例である.

入力例(Sample Input)	出力例(Sample Output)
`7 5 w@ww@w@ w.wwwww wwww@ww wwwwww ww.@w.`	`w@... w.ww.ww wwww@ww www.ww ...@w.`

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