Territory(縄張り) - joi2009-day3

出典: 第8回日本情報オリンピック 春季トレーニング合宿

時間制限: 1秒

メモリ制限: 64MB

あなたはジョイ(JOI)君という名の1匹の犬を飼っている. ジョイ君の散歩は東西南北のいずれかに1歩ずつ移動することを繰り返す. あるときあなたはジョイ君の縄張りの大きさを調べたいと思い記録装置を取り付けた. 記録装置はジョイ君の東西南北の1 歩ずつの移動にあわせてN, E, S, W の4文字を記録する. またジョイ君が散歩を終え停止すると移動の終わりを示すQを記録する.

あなたは, ジョイ君が囲った部分をジョイ君の縄張りだと思うことにした. 移動記録に基づきジョイ君の縄張りの面積を求めるプログラムを作成せよ. ただし, 1辺がジョイ君の1 歩である正方形の面積を1とする. 「ジョイ君が囲った部分」とは, どの辺もジョイ君が散歩中に通った軌跡の一部である図形(これは1個以上の重ならない多角形からなる)のうち面積が最大のものである. 囲った部分が存在しない場合は0を出力せよ.

Input.

入力ファイルはterritory.inである.

各行には5種類のアルファベットN, E, S, W, Qの中の1文字が書かれている.ジョイ君は必ず1歩以上の移動を行う. 書かれている文字がQの場合は, その行が入力の最終行である.

Output.

出力は標準出力に行うこと. 縄張りの面積を表す整数のみを出力せよ.

採点基準

採点用データのうち, 配点の30% 分は行数が1000行を超えない. また, 全てのデータにおいて行数は100 000 = 10^5 行を超えない.

例1

territory.in	標準出力
S W W N E E E S E N W Q	3

例2

territory.in	標準出力
E N E N S W S W S W Q	0