Problem:


ザ・スクエアーズ

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

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

図1

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

現在向いている方向の、右、前、左、後のマス目を順番に調べ、最初に見つけた、空いている通路または非常口の方向に向きを変えます。そのようなマス目が無い場合は向きを変えません。

 目の前のマス目が空いていて、他の人の目の前のマス目になっていない場合は移動します。同じマス目を目の前のマスとする人が複数いる場合は、そのマス目の、東、北、西、南のマス目にいる人の順で選択された 1 人が移動します。

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

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

# : 壁

. : 床

X : 非常口

E : 東を向いている人

N : 北を向いている人

W : 西を向いている人

S : 南を向いている人

なお、迷路と外部との境界は壁 # または非常口 X のいずれかです。また、巨大迷路の中には、人が必ず１人以上います。

Input

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

W H
str1
str2
:
strH

1 行目に迷路の横方向の大きさ W、縦方向の大きさ H (1 ≤ W, H ≤ 30) が与えられます。続く H 行に迷路の i 行目を表す文字列 stri (長さ W) が与えられます。

データセットの数は 50 を超えません。

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



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


Sample output:
8
NA
9
16
10

Submission status: Runtime Error

Solution code:
import copy
def hinan():
    ans = []
    while True:
        n = raw_input().split(" ")
        if n == ["0" ,"0"]:
            for an in ans:
                print an
            break
        elif len(n) == 2:
            xs = []
            k = int(n[1])
            for m in range(k):
                n = map(str,raw_input())
                xs.append(n)
            for time in range(181):
                check = []
                for i in range(len(xs)):
                    if not any(x in xs[i] for x in ["W","E","N","S"]):
                        check.append(True)
                        continue
                    else:
                        check.append(False)
                    for j in range(len(xs[i])):
                        if xs[i][j] == "S":
                            if xs[i][j - 1] in ["." ,"X"]:
                                xs[i][j] = "W"
                            elif xs[i + 1][j] in ["." ,"X"]:
                                xs[i][j] = "S"
                            elif xs[i][j + 1] in ["." ,"X"]:
                                xs[i][j] = "E"
                            elif xs[i - 1][j] in ["." ,"X"]:
                                xs[i][j] = "N"
                        elif xs[i][j] == "W":
                            if xs[i - 1][j] in ["." ,"X"]:
                                xs[i][j] = "N"
                            elif xs[i][j - 1] in ["." ,"X"]:
                                xs[i][j] = "W"
                            elif xs[i + 1][j] in ["." ,"X"]:
                                xs[i][j] = "S"
                            elif xs[i][j + 1] in ["." ,"X"]:
                                xs[i][j] = "E"
                        elif xs[i][j] == "E":
                            if xs[i + 1][j] in ["." ,"X"]:
                                xs[i][j] = "S"
                            elif xs[i][j + 1] in ["." ,"X"]:
                                xs[i][j] = "E"
                            elif xs[i - 1][j] in ["." ,"X"]:
                                xs[i][j] = "N"
                            elif xs[i][j - 1] in ["." ,"X"]:
                                xs[i][j] = "W"
                        elif xs[i][j] == "N":
                            if xs[i][j + 1] in ["." ,"X"]:
                                xs[i][j] = "E"
                            elif xs[i - 1][j] in ["." ,"X"]:
                                xs[i][j] = "N"
                            elif xs[i][j - 1] in ["." ,"X"]:
                                xs[i][j] = "W"
                            elif xs[i + 1][j] in ["." ,"X"]:
                                xs[i][j] = "S"
                ys = copy.deepcopy(xs)
                if all(check):
                    ans.append(time)
                    break
                for i in range(len(xs)):
                    for j in range(len(xs[i])):
                        if xs[i][j] == "S":
                            if xs[i + 1][j + 1] != "W":
                                if xs[i + 1][j] == "X":
                                    ys[i][j] = "."
                                    continue
                                else:
                                    ys[i + 1][j] ,ys[i][j] = "S" ,"."
                                    continue
                        elif xs[i][j] == "E":
                            if j < len(xs[i]) - 2:
                                if xs[i][j + 2] != "W" and xs[i - 1][j + 1] != "S":
                                    if xs[i][j + 1] == "X":
                                        ys[i][j] = "."
                                        continue
                                    else:
                                        ys[i][j + 1] ,ys[i][j] = "E" ,"."
                                        continue
                            else:
                                if xs[i][j + 1] == "X":
                                    ys[i][j] = "."
                                    continue
                                else:
                                    ys[i][j + 1] ,ys[i][j] = "E" ,"."
                                    continue
                        elif xs[i][j] == "W":
                            if xs[i][j - 1] == "X":
                                ys[i][j] = "."
                                continue
                            else:
                                ys[i][j - 1] ,ys[i][j] = "W" ,"."
                                continue
                        elif xs[i][j] == "N":
                            if i > 1:
                                if xs[i - 1][j + 1] != "W" and xs[i - 2][j] != "S" and xs[i - 1][j - 1] != "E":
                                    if xs[i - 1][j] == "X":
                                        ys[i][j] = "."
                                        continue
                                    elif xs[i - 1][j] == ".":
                                        ys[i - 1][j] ,ys[i][j] = "N" ,"."
                                        continue
                            else:
                                if xs[i - 1][j + 1] != "W" and xs[i - 1][j - 1] != "E":
                                    if xs[i - 1][j] == "X":
                                        ys[i][j] = "."
                                        continue
                                    elif xs[i - 1][j] == ".":
                                        ys[i - 1][j] ,ys[i][j] = "N" ,"."
                                        continue
                xs = ys
            else:
                ans.append("NA")
hinan()

Submission status: Runtime Error

Solution code:
def add(x ,y): return x + y
def hinan():
    ans ,houi ,vector = [] ,[[0 ,1] ,[-1 ,0] ,[0 ,-1] ,[1 ,0] ,[0 ,1] ,[-1 , 0] ,[1 ,0]] ,["E" ,"N" ,"W" ,"S"]
    while True:
        n = raw_input().split(" ")
        if n == ["0" ,"0"]:
            for an in ans:
                print an
            break
        else:
            xs =[[] ,[] ,[]]
            for i in range(int(n[1])):
                n = raw_input()
                for k in range(3):
                    xs[k] = xs[k] + [[[i ,j] for j in range(len(n)) if n[j] != "#"] ,[[[i ,j] ,houi[vector.index(n[j])]] for j in range(len(n)) if n[j] in vector] ,[[i ,j] for j in range(len(n)) if n[j] == "X"]][k]
            for time in range(181):
                if len(xs[1]) == 0:
                    ans.append(time)
                    break
                else:
                    for i in xs[1]:
                        for j in range(4):
                            look_point = map(add ,i[0] ,houi[houi.index(i[1]) - 1 + j])
                            if look_point in xs[0]:
                                i[1] = houi[houi.index(i[1]) - 1 + j]
                                break
                    go_point ,where = [] ,[i[0] for i in xs[1]]
                    for i in xs[1]:
                        go_point.append(map(add ,i[0] ,i[1]))
                    for i in range(len(go_point)):
                        if go_point.count(go_point[i]) > 1:
                            if not go_point[i] in where:
                                for j in range(4):
                                    if xs[1][i] == [map(add ,go_point[i] ,houi[j]) ,houi[j + 2]]:
                                        xs[1][i][0] ,where[i] = go_point[i] ,go_point[i]
                                    elif [map(add ,go_point[i] ,houi[j]) ,houi[j + 2]] in xs[1]:
                                        break
                        else:
                            xs[1][i][0] ,where[i] = go_point[i] ,go_point[i]
                        if xs[1][i][0] in xs[2]:
                            del xs[1][i]
                    print xs ,look_point ,go_point ,where
            else:
                ans.append("NA")
hinan()

Submission status: Runtime Error

Solution code:
def hinan():
    ans ,houi ,vector = [] ,[[0 ,1] ,[-1 ,0] ,[0 ,-1] ,[1 ,0] ,[0 ,1] ,[-1 , 0] ,[1 ,0]] ,["E" ,"N" ,"W" ,"S"]
    while True:
        n = raw_input().split(" ")
        if n == ["0" ,"0"]:
            for an in ans:
                print an
            break
        else:
            xs =[[] ,[] ,[]]
            for i in range(int(n[1])):
                n = raw_input()
                xs = [xs[l] + [[[i ,j] for j in range(len(n)) if n[j] != "#"] ,[[[i ,j] ,houi[vector.index(n[j])]] for j in range(len(n)) if n[j] in vector] ,[[i ,j] for j in range(len(n)) if n[j] == "X"]][l] for l in range(3)]
            for time in range(181):
                if len(xs[1]) == 0:
                    ans.append(time)
                    break
                else:
                    for i in xs[1]:
                        where ,look_point = [l[0] for l in xs[1]] ,[[k for k in [[i[0][l] + houi[houi.index(i[1]) - 1 + j][l] for l in range(2)] for j in range(4)] if k in xs[0] and not k in where]
                        if len(look_point) > 0:
                            i[1] = [look_point[0][s] - i[0][s] for s in range(2)]
                    go_point = [[i[0][l] + i[1][l] for l in range(2)] for i in xs[1]]
                    for i in range(len(go_point)):
                        if go_point.count(go_point[i]) > 1:
                            if not go_point[i] in where:
                                for j in range(4):
                                    if xs[1][i] == [[go_point[i][l] + houi[j][l] for l in range(2)] ,houi[j + 2]]:
                                        xs[1][i][0] ,where[i] = go_point[i] ,go_point[i]
                                    elif [[go_point[i][l] + houi[j][l] for l in range(2)] ,houi[j + 2]] in xs[1]:
                                        break
                        else:
                            xs[1][i][0] ,where[i] = go_point[i] ,go_point[i]
                    xs[1] = [i for i in xs[1] if not i[0] in xs[2]]
            else:
                ans.append("NA")
hinan()

Submission status: Runtime Error

Solution code:
def hinan():
    ans ,houi ,vector = [] ,[[0 ,1] ,[-1 ,0] ,[0 ,-1] ,[1 ,0] ,[0 ,1] ,[-1 , 0] ,[1 ,0]] ,["E" ,"N" ,"W" ,"S"]
    while True:
        n = raw_input().split(" ")
        if n == ["0" ,"0"]:
            for an in ans:
                print an
            break
        else:
            xs =[[] ,[] ,[]]
            for i in range(int(n[1])):
                n = raw_input()
                xs = [xs[l] + [[[i ,j] for j in range(len(n)) if n[j] != "#"] ,[[[i ,j] ,houi[vector.index(n[j])]] for j in range(len(n)) if n[j] in vector] ,[[i ,j] for j in range(len(n)) if n[j] == "X"]][l] for l in range(3)]
            for time in range(181):
                print xs
                if len(xs[1]) == 0:
                    ans.append(time)
                    break
                else:
                    for i in xs[1]:
                        where = [l[0] for l in xs[1]]
                        if len([k for k in [[i[0][l] + houi[houi.index(i[1]) - 1 + j][l] for l in range(2)] for j in range(4)] if k in xs[0] and not k in where]) > 0:
                            i[1] = [[k for k in [[i[0][l] + houi[houi.index(i[1]) - 1 + j][l] for l in range(2)] for j in range(4)] if k in xs[0] and not k in where][0][s] - i[0][s] for s in range(2)]
                    go_point = [[i[0][l] + i[1][l] for l in range(2)] for i in xs[1]]
                    for i in range(len(go_point)):
                        if go_point.count(go_point[i]) > 1:
                            if not go_point[i] in where:
                                for j in range(4):
                                    if xs[1][i] != [[go_point[i][l] + houi[j][l] for l in range(2)] ,houi[j + 2]] and [[go_point[i][l] + houi[j][l] for l in range(2)] ,houi[j + 2]] in xs[1]:
                                        go_point[i] = xs[1][0]
                                        break
                    xs[1] = [[go_point[i] ,xs[1][i][1]] for i in range(len(xs[1])) if not go_point[i] in xs[2]]
            else:
                ans.append("NA")
hinan()

Submission status: Runtime Error

Solution code:
def hinan():
    ans ,houi ,vector = [] ,[[0 ,1] ,[-1 ,0] ,[0 ,-1] ,[1 ,0] ,[0 ,1] ,[-1 , 0] ,[1 ,0]] ,["E" ,"N" ,"W" ,"S"]
    while True:
        n = raw_input().split(" ")
        if n == ["0" ,"0"]:
            for an in ans:
                print an
            break
        else:
            xs =[[] ,[] ,[]]
            for i in range(int(n[1])):
                n = raw_input()
                xs = [xs[l] + [[[i ,j] for j in range(len(n)) if n[j] != "#"] ,[[[i ,j] ,houi[vector.index(n[j])]] for j in range(len(n)) if n[j] in vector] ,[[i ,j] for j in range(len(n)) if n[j] == "X"]][l] for l in range(3)]
            for time in range(181):
                if len(xs[1]) == 0:
                    ans.append(time)
                    break
                else:
                    for i in xs[1]:
                        where = [l[0] for l in xs[1]]
                        if len([k for k in [[i[0][l] + houi[houi.index(i[1]) - 1 + j][l] for l in range(2)] for j in range(4)] if k in xs[0] and not k in where]) > 0:
                            i[1] = [[k for k in [[i[0][l] + houi[houi.index(i[1]) - 1 + j][l] for l in range(2)] for j in range(4)] if k in xs[0] and not k in where][0][s] - i[0][s] for s in range(2)]
                    go_point = [[i[0][l] + i[1][l] for l in range(2)] for i in xs[1]]
                    for i in range(len(go_point)):
                        if go_point.count(go_point[i]) > 1:
                            if not go_point[i] in where:
                                for j in range(4):
                                    if xs[1][i] != [[go_point[i][l] + houi[j][l] for l in range(2)] ,houi[j + 2]] and [[go_point[i][l] + houi[j][l] for l in range(2)] ,houi[j + 2]] in xs[1]:
                                        go_point[i] = xs[1][0]
                                        break
                    xs[1] = [[go_point[i] ,xs[1][i][1]] for i in range(len(xs[1])) if not go_point[i] in xs[2]]
            else:
                ans.append("NA")
hinan()

Submission status: Runtime Error

Solution code:
from sys import stdin
readline = stdin.readline


from itertools import product

N, W, S, E = (0, -1), (-1, 0), (0, 1), (1, 0)
BLANK = ('.', 'X')
DIRECTION = {
    'N': N,
    'W': W,
    'S': S,
    'E': E,
}
check_priority = {
    N: (E, N, W, S),
    W: (N, W, S, E),
    S: (W, S, E, N),
    E: (S, E, N, W),
    }
step_priority = (E, N, W, S)


def search_people(sq):
    people = []
    for y, x in product(range(h), range(w)):
        if sq[y][x] in DIRECTION:
            sq[y][x] = person = Person(x, y, DIRECTION[sq[y][x]], sq)
            people.append(person)
    return people


class Person:
    def __init__(self, x, y, direction, sq):
        self.x, self.y = x, y
        self.direction = direction
        self.sq = sq
        self.evacuating = True

    def check_direction(self):
        for direction in check_priority[self.direction]:
            dx, dy = direction
            if self.sq[self.y + dy][self.x + dx] in BLANK:
                self.direction = direction
                break

    def check_stepable(self):
        dx, dy = self.direction
        x, y = self.x + dx, self.y + dy
        if self.sq[y][x] == 'X':
            return True
        for dx, dy in step_priority:
            tmp = self.sq[y + dy][x + dx]
            if not isinstance(tmp, Person):
                continue
            if tmp == self:
                self.stepable = True
                break
            dx, dy = tmp.direction
            if tmp.x + dx == x and tmp.y + dy == y:
                self.stepable = False
                break

    def __repr__(self):
        return "'P'"

    def step(self):
        if self.stepable:
            dx, dy = self.direction
            self.sq[self.y][self.x] = '.'
            self.x += dx
            self.y += dy
            if self.sq[self.y][self.x] == '.':
                self.sq[self.y][self.x] = self
            else:
                self.evacuating = False


while True:
    w, h = map(int, readline().split())
    if w == 0:
        break
    squares = [list(readline().strip()) for _ in range(h)]
    people = search_people(squares)

    for i in range(180):
        for pi in people:
            pi.check_direction()
        for pi in people:
            pi.check_stepable()
        for pi in people:
            pi.step()
        people = [pi for pi in people if pi.evacuating]
        if len(people) == 0:
            print(i + 1)
            break
    else:
        print('NA')

Submission status: Runtime Error

Solution code:
from sys import stdin
readline = stdin.readline

from itertools import product

N, W, S, E = (0, -1), (-1, 0), (0, 1), (1, 0)
BLANK = ('.', 'X')
DIRECTION = {
    'N': N,
    'W': W,
    'S': S,
    'E': E,
}
check_priority = {
    N: (E, N, W, S),
    W: (N, W, S, E),
    S: (W, S, E, N),
    E: (S, E, N, W),
    }
step_priority = (E, N, W, S)


def search_people(sq):
    people = []
    for y, x in product(range(h), range(w)):
        if sq[y][x] in DIRECTION:
            sq[y][x] = person = Person(x, y, DIRECTION[sq[y][x]], sq)
            people.append(person)
    return people


class Person:
    def __init__(self, x, y, direction, sq):
        self.x, self.y = x, y
        self.direction = direction
        self.sq = sq
        self.evacuating = True

    def check_direction(self):
        for direction in check_priority[self.direction]:
            dx, dy = direction
            if self.sq[self.y + dy][self.x + dx] in BLANK:
                self.direction = direction
                break

    def check_stepable(self):
        dx, dy = self.direction
        x, y = self.x + dx, self.y + dy
        if self.sq[y][x] == 'X':
            self.stepable = True
            return
        for dx, dy in step_priority:
            tmp = self.sq[y + dy][x + dx]
            if not isinstance(tmp, Person):
                continue
            if tmp == self:
                self.stepable = True
                break
            dx, dy = tmp.direction
            if tmp.x + dx == x and tmp.y + dy == y:
                self.stepable = False
                break

    def __repr__(self):
        return "'P'"

    def step(self):
        if self.stepable:
            dx, dy = self.direction
            self.sq[self.y][self.x] = '.'
            self.x += dx
            self.y += dy
            if self.sq[self.y][self.x] == '.':
                self.sq[self.y][self.x] = self
            else:
                self.evacuating = False


while True:
    w, h = map(int, readline().split())
    if w == 0:
        break
    squares = [list(readline().strip()) for _ in range(h)]
    people = search_people(squares)

    for i in range(180):
        for pi in people:
            pi.check_direction()
        for pi in people:
            pi.check_stepable()
        for pi in people:
            pi.step()
        people = [pi for pi in people if pi.evacuating]
        if len(people) == 0:
            print(i + 1)
            break
    else:
        print('NA')