iwashiの収穫祭

問題

これは何年前か、誰かがちょんぎった1日のお話。

明日は謎の生物iwashiがつちからはえてきます。iwashiはTSG国にのみ生息する生き物で、天敵はつばめです。その味からTSG国の特産物になってます。

TSG国のfiord君はiwashiの収穫をしたいと思っています。ただ、iwashiは凶暴な生き物で、群れをなして囲まれてしまうととても危険です。

今回、TSG国屈指の大企業hakata社が事前にiwashiのはえてくる場所を正確に予測してくれています。

安全にfiord君がiwashiの収穫を行えるよう、ナビゲートしてあげてください。

ルール

• TSG国はH×Wのマス目で表現されています。北西が(1,1)、南東が(H,W)で表現されます。各マスは「通路」か「壁」のどちらかです。各マスは東西南北の隣接したマスとつながっており、斜めへの移動は出来ません。fiord君やiwashiは通路上を移動し、壁のマスへ行くことは出来ません。
• この日はTターンからなります。fiord君は各ターン東西南北のどちらかの方向を選び、1マス進めます（進まなくてもいいです）。進んだ先にiwashiがいるなら収穫を試みます。
• iwashiは毎ターン、fiord君か他のiwashiの群れか、近い方へ向けて毎ターンfiord君と同じ速度で移動します。
• fiord君が同時に収穫できるiwashiは5匹までです。6匹以上iwashiがいるマスへfiord君が行くと、逆に襲われてケガをしてしまいます。ケガをすると、5ターン治療に費やしてしまうので、気を付けましょう。なお、何故か治療中のfiord君をiwashiは認識できません。
• Tターンで収穫するiwashiが最大になるようfiord君の行動を教えてあげて下さい。

iwashiの行動について

具体的には、以下のアルゴリズムで動作します。

• (1,1)→(1,2)→…→(1,W)→(2,1)→…→(2,W)→(3,1)→…→(H,W)の順に、以下のことを行います。
  1. iwashiがいないなら次へ行きます。
  2. 既にそのマスへ外からiwashiがやってくることが分かっているなら元々そのマスにいたiwashiは動きません。
  3. そうでなければ、他のiwashiのいるマスと治療中でないfiord君をソース（距離0）として「最短距離」のマップを作成。
  4. 北→東→南→西の順に、現在位置よりも3のマップ上で距離が短いマスを探し、見つけたらそちらへ移動します。

また、各ターンは、

1. fiord君移動(治療中は動けません)
2. iwashi移動（運悪くiwashiがfiord君のマスへ突っ込むときがあります。）
3. iwashiがつちからはえてくる(fiord君がいるマスへはえてくる可能性もあります)
4. fiord君収穫に挑戦（fiord君がケガをしている間は収穫できません。ケガもしません。iwashiが素通りすることもあります）
   • fiord君が治療中なら収穫出来ません。fiord君のマスにiwashiがいても何も起こりません。
   • fiord君のいるマスに5匹以下のiwashiがいるなら、そのiwashi達を収穫します。
   • fiord君のいるマスに6匹以上のiwashiがいるなら、fiord君は全治5ターンのケガをします。iwashiはつばめが嬉々として狩っていくので消滅します。

の順になります。

入力

標準入力を用い、以下の形式で与えられます。

H W T N
Px Py
S1
S2
...
SH
x1 y1 t1
x2 y2 t2
...
xN yN tN

• TSG国の区画はH×Wです。その区画は{Si | 0≦i≦H-1}になっています。0≦i≦H-1で|Si|=Wが成立し、Sij="#"でそのマスが壁、Sij="."で通路であることを示します。外周は"#"で囲まれていることが保証されています。
• 現在のfiord君の位置は(Px, Py)です。周囲が壁て囲まれていて動けない可能性があります。
• また、この日にfiord君はTターン行動可能です。hakata社のエスパーによると今日はN匹のiwashiがつちからはえてくるらしいです。
• i匹目(1≦i≦N)のiwashiは位置(xi, yi)に現在からtiターン後につちからはえてきます。ti=0は既にはえているiwashiです。

出力

S

• 標準出力で、fiord君のTターンの移動方法をT文字の文字列Sとして出力してください。
• Siが"N"、"E"、"W"、"S"のどれかの時、それぞれの方角に応じた方向へfiord君は動こうとします。
• それ以外の文字だった場合や、|S|>Tの時のSi(i>T)、|S|<Tの時の|S|ターン以降の動作は「移動を試みない」という扱いをします。

スコア、テストケース、勝敗の決定方法

テストケースは以下のものを使用します。

• 共通のもの
  • H=22
  • W=22
• tiny(1ケース)
  • N=50
  • T=150
  • 壁と通路の比率: 外周を除いて壁は15%で無作為に生成
• little(6ケース)
  • N=250
  • T=1000
  • 壁と通路の比率: 外周を除いて壁は25%で無作為に生成
• much(6ケース)
  • N=3000
  • T=1000
  • 壁と通路の比率: 外周を除いて壁は25%で無作為に生成
• challenge(3ケース)
  • N=1000
  • T=1000
  • 壁と通路の比率: 外周を除いて壁は47.5%で作為的に生成

スコアは各テストケースで{iwashiの収穫数}/Nで求めます。勝敗は各テストケースのスコアの総和で求めます。

今回の五月祭では全体を通して赤vs青の形式を取っています。この大戦では、ceil(100*(勝者のスコアの総和 - 敗者のスコアの総和))ptが勝利したチームに加算されます。

サンプルコード

以下は、この問題に対して不正でない出力を行う(かつ正の得点を得ると推定される)C++のサンプルコードである。

https://gist.github.com/hakatashi/c93259d9e88278d4ad42f86ceb4c98f1

入力例

10 10 150 50
2 3
##########
#....#...#
##.#.....#
#.##.....#
#........#
####.....#
#....##..#
###......#
##...##..#
##########
5 2 0
5 7 4
5 6 17
7 5 23
6 8 24
6 3 24
9 6 28
6 8 32
9 3 34
3 2 35
4 8 35
9 5 43
9 4 44
3 5 46
9 5 54
5 5 63
5 9 68
4 7 71
7 5 77
4 8 78
6 4 78
8 5 80
8 7 80
5 9 82
8 6 83
9 6 87
4 9 92
9 2 99
2 2 100
7 5 102
9 4 102
5 7 103
9 6 103
8 3 105
7 5 106
4 7 106
8 6 108
3 2 114
3 3 117
5 9 120
9 9 121
4 5 123
8 4 124
8 8 127
2 5 129
3 7 136
2 7 139
9 9 139
7 3 145
3 7 148

出力例

NWWNSEWNSEWSNWWSNWSESESEEWWNNNWSWWENENWSNNWWNNNNEENEWNWWSWWNSNSSNSNNWENESSSSWWSENWSSWEWNESSENWSSEEWNNEENEESSNSNWSENESSWSWNWSENWWSNSNESEWNEENNSWSNSENWS