The Squares

Time Limit : 1 sec, Memory Limit : 65536 KB

Problem F: ザ・スクエアーズ

この度、有名なテーマパークに、巨大迷路ザ・スクエアーズが新しく完成しました。 消防署の指導により避難訓練をしなければなりませんが、巨大迷路なだけに訓練にかかる時間を予測することができません。そこで、あなたは以下の仕様をもとに避難訓練シミュレータを開発することになりました。

巨大迷路は図 1 に示すように、横 W 、縦 H の W × H 個のマス目で表わされます。各マス目は、通路(白いマス目)、壁(茶色いマス目) 、非常口(緑のマス目)のいずれかです。図中の○は人を表し、その中のアルファベット(E、W、S、N)はその人が向いている方角(東西南北)を表しています。図は上方向が北になるように描かれています。


図1


巨大迷路内にいる人は最初、東西南北のいずれかの方向を向いて立っています。各人は 1 秒単位で同時に次に示す手順で移動を試みます。

  1. 現在向いている方向の、右、前、左、後のマス目を順番に調べ、最初に見つけた、空いている通路または非常口の方向に向きを変えます。そのようなマス目が無い場合は向きを変えません。
  2. 目の前のマス目が空いていて、他の人の目の前のマス目になっていない場合は移動します。同じマス目を目の前のマスとする人が複数いる場合は、そのマス目の、東、北、西、南のマス目にいる人の順で選択された 1 人が移動します。

移動後に非常口に到着した人は、無事避難し迷路内から消えます。

与えられた巨大迷路と人の位置情報を入力とし、全ての人が避難し終える時間を出力するプログラムを作成してください。 脱出に 180 秒より長い時間を要する場合は NA と出力して下さい。 迷路と人の位置情報は、 H 行 W 列の文字によって与えられます。ただし、 H 、W は 1 以上 30 以下の整数とします。各文字の意味は以下のとおりです。

#
.(ピリオド)床
X 非常口
E 東を向いている人
N 北を向いている人
W 西を向いている人
S 南を向いている人

なお、迷路と外部との境界は壁 # または非常口 X のいずれかです。

Input

複数のデータセットの並びが入力として与えられます。 入力の終わりはゼロふたつの行で示されます。 各データセットは以下のとおりです。

1 行目 迷路の大きさ横 W 縦 H (整数 整数 ; 半角空白区切り)
2 行目 迷路の 1 行目の情報 (半角英文字列)
:
H+1 行目 迷路の H 行目の情報

Output

入力データセットごとに、全ての人が避難し終える時間を出力します。

Sample Input

10 3
##########
#E.......X
##########
4 4
####
#N.#
#..X
####
5 5
#####
#N..#
###.X
#S..#
#####
6 6
######
#..#X#
#.EE.#
####N#
#....#
######
8 8
##X#####
#....E.#
#####.##
#.#...##
#.W.#..#
#.#.N#.X
#X##.#.#
########
0 0

Output for the Sample Input

8
NA
9
16
10

Source: PC Koshien 2009 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2009-11-14
http://www.pref.fukushima.jp/pc-concours/