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: Accepted

Solution code:
from sys import stdin
from itertools import chain
head = [[8,1,2,4],[1,2,4,8],[2,4,8,1],[4,8,1,2]]

while(True):
    W,H = map(int, stdin.readline().split())
    m = [[0]*W for _ in range(H)]
    ps = []
    if not (W or H): break
    flag = True
    for h in range(H):
        s = stdin.readline()
        if "X" in s: flag = False
        for w in range(W):
            if s[w] in [".", "X", "E", "N", "W", "S"]:
                m[h][max(0,w-1)] |= 1
                m[min(H-1,h+1)][w] |= 2
                m[h][min(W-1,w+1)] |= 4
                m[max(0,h-1)][w] |= 8
            if s[w] in ["E", "N", "W", "S"]:
                ps.append([h,w,["E", "N", "W", "S"].index(s[w])])
            if s[w] == "X":
                m[h][w] |= 16
    # if flag:
    #     print("NA")
    #     continue
    if W <= 2 or H <= 2:
        print(1)
        continue
    # print(ps)
    # for n in m:
    #     print(n)
    ttt = 0
    while(True):
        ttt += 1
        if ttt > 180: print("NA"); break
        # import time
        # time.sleep(1)
        mt = [[0]*W for _ in range(H)]
        for p in ps:
            mt[p[0]][p[1]] |= 1
        dest = []
        # for mmm in mt:
        #     print(mmm)
        # print()
        # print([a[:2] for a in ps])
        for pi,p in enumerate(ps):
            for i in range(4):
                if head[p[2]][i] & m[p[0]][p[1]]:
                    d = head[p[2]][i]
                    if   d == 1 and not [p[0],p[1]+1] in [a[:2] for a in ps]: p[2] = 0; dest.append([pi,2,p[0],p[1]+1]); break
                    elif d == 2 and not [p[0]-1,p[1]] in [a[:2] for a in ps]: p[2] = 1; dest.append([pi,3,p[0]-1,p[1]]); break
                    elif d == 4 and not [p[0],p[1]-1] in [a[:2] for a in ps]: p[2] = 2; dest.append([pi,0,p[0],p[1]-1]); break
                    elif d == 8 and not [p[0]+1,p[1]] in [a[:2] for a in ps]: p[2] = 3; dest.append([pi,1,p[0]+1,p[1]]); break
            else:
                dest.append([pi,(p[2]+2)&3,p[0],p[1]])
        dest = sorted(dest,key=lambda x: (x[2:],x[1]))
        # print(dest)
        # for mmm in mt:
        #     print(mmm)
        # print("ps = ",ps,dest)
        dellist = []
        for pi,d,dy,dx in dest:
            # print(W,H,dy,dx,mt)
            if not mt[dy][dx]:
                # print("move",W,H,ps[pi][:2],dy,dx)
                mt[dy][dx] |= 1
                ps[pi][:2] = [dy,dx]
            if m[ps[pi][0]][ps[pi][1]] & 16:
                # print("OUT")
                # print(ttt)
                # time.sleep(3)
                dellist.append(pi)
        # print(dellist)
        for idx in sorted(dellist)[::-1]:
            del ps[idx]
        if not len(ps):
            print(ttt)
            break

    # ms = [stdin.readline() for _ in range(H)]
    # print(m)
    # from pprint import pprint
    # print(ps)
    # for n in m:
    #     print(n)
    # print()

Submission status: Accepted

Solution code:
from sys import stdin
# from line_profiler import LineProfiler

def main():

    head = [[8,1,2,4],[1,2,4,8],[2,4,8,1],[4,8,1,2]]

    while(True):
        W,H = map(int, stdin.readline().split())
        m = [[0]*W for _ in range(H)]
        ps = []
        if not (W or H): break
        for h in range(H):
            s = stdin.readline()
            for w in range(W):
                if s[w] in [".", "X", "E", "N", "W", "S"]:
                    m[h][max(0,w-1)] |= 1
                    m[min(H-1,h+1)][w] |= 2
                    m[h][min(W-1,w+1)] |= 4
                    m[max(0,h-1)][w] |= 8
                if s[w] in ["E", "N", "W", "S"]:
                    ps.append([h,w,["E", "N", "W", "S"].index(s[w])])
                if s[w] == "X":
                    m[h][w] |= 16
        if W <= 2 or H <= 2:
            print(1)
            continue
        ttt = 0
        while(True):
            ttt += 1
            if ttt > 180: print("NA"); break
            dest = []
            positions = [a[:2] for a in ps]
            for pi,p in enumerate(ps):
                for i in range(4):
                    if head[p[2]][i] & m[p[0]][p[1]]:
                        d = head[p[2]][i]
                        if   d == 1 and not [p[0],p[1]+1] in positions: p[2] = 0; dest.append([pi,2,p[0],p[1]+1]); break
                        elif d == 2 and not [p[0]-1,p[1]] in positions: p[2] = 1; dest.append([pi,3,p[0]-1,p[1]]); break
                        elif d == 4 and not [p[0],p[1]-1] in positions: p[2] = 2; dest.append([pi,0,p[0],p[1]-1]); break
                        elif d == 8 and not [p[0]+1,p[1]] in positions: p[2] = 3; dest.append([pi,1,p[0]+1,p[1]]); break
                else:
                    dest.append([pi,(p[2]+2)&3,p[0],p[1]])
            dest = sorted(dest,key=lambda x: (x[2:],x[1]))
            dellist = []
            for pi,d,dy,dx in dest:
                if not [dy,dx] in positions: positions.append([dy,dx]); ps[pi][:2] = [dy,dx]
                if m[ps[pi][0]][ps[pi][1]] & 16: dellist.append(pi)
            for idx in sorted(dellist)[::-1]: del ps[idx]
            if not len(ps): print(ttt); break

if __name__ == "__main__":
    # prf = LineProfiler()
    # prf.add_function(main)
    # prf.runcall(main)
    # prf.print_stats()
    main()

Submission status: Accepted

Solution code:
import sys

direction = {'N' : 0, 'E' : 1, 'S' : 2, 'W' : 3}
step = [( -1, 0 ), ( 0, 1 ), ( 1, 0 ), ( 0, -1 )]
vv = []

while True:
    W, H = map( int, sys.stdin.readline().rstrip().split() )
    if W == 0 and H == 0: break
    m = [ list( sys.stdin.readline().strip() ) for i in xrange( H ) ]
    people = [ [ i, j, direction[ m[i][j] ] ] for i in xrange( H ) for j in range( W )
               if m[i][j] in "NESW" ]
    time = 0
    while any( people ):
        time += 1
        if time > 180:
            time = -1
            break
        sched = []
        for n in xrange( len( people ) ):
            if people[n] is None: continue
            x, y, d = people[n]
            for i in range(1, -3, -1):
                    dx, dy = step[(d + i) % 4]
                    if 0 <= x+dx < H and 0 <= y+dy < W and m[x+dx][y+dy] in "X.":
                        people[n][2] = (d + i) % 4
                        beat = True
                        for k in range( len( sched ) ):
                            xx, yy, dd = sched[k][1:]
                            if ( x+dx, y+dy ) == ( xx, yy ):
                                if dd < (d + i) % 4:
                                    sched[k] = ( n, x+dx, y+dy, (d + i) % 4 )
                                    beat = False
                                    break
                                else:
                                    beat = False
                                    break
                        if beat:
                            sched.append( ( n, x+dx, y+dy, (d + i) % 4 ) )
			break
        for ( k, x, y, d ) in sched:
            m[ people[k][0] ][ people[k][1] ] = '.'
            if m[x][y] == 'X':
                people[k] = None
            else:
                m[x][y] = 'H'
                people[k] = list([x, y, d])
    if time >= 0:
        vv.append(time)
    else:
        vv.append('NA')

for v in vv:
    print v

Submission status: Accepted

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[i] in where or not go_point[i] in xs[0]:
                            go_point[i] = xs[1][i][0]
                        else:
                            if go_point.count(go_point[i]) > 1:
                                for j in range(4):
                                    if xs[1][i] == [[go_point[i][l] + houi[j][l] for l in range(2)] ,houi[j + 2]]:
                                        break
                                    elif [[go_point[i][l] + houi[j][l] for l in range(2)] ,houi[j + 2]] in xs[1]:
                                        go_point[i] = xs[1][i][0]
                                        break
                    else:
                        xs[1] = [k for k in [[go_point[i] ,xs[1][i][1]] for i in range(len(xs[1]))] if not k[0] in xs[2]]
            else:
                ans.append("NA")
hinan()

Submission status: Accepted

Solution code:
dd = ((1, 0), (0, -1), (-1, 0), (0, 1))
ENWS = "ENWS"
ds = [-1, 0, 1, 2]
ss = [2, 3, 0, 1]

while 1:
    W, H = map(int, input().split())
    if W == H == 0:
        break
    S = [input() for i in range(H)]

    ps = []; U = [[-1]*W for i in range(H)]
    for i in range(H):
        for j, c in enumerate(S[i]):
            if c in ENWS:
                ps.append([i, j, ENWS.index(c)])
                U[i][j] = 1
            elif c == '#':
                U[i][j] = W*H
    rest = len(ps)
    t = 0
    while rest > 0 and t <= 180:
        for p in ps:
            y, x, c = p
            if c == -1:
                continue
            for d in ds:
                dx, dy = dd[(c+d) % 4]
                nx = x + dx; ny = y + dy
                if U[ny][nx] == -1:
                    p[2] = (c+d) % 4
                    break
        ps.sort(key = lambda x: ss[x[2]])
        qs = []
        for p in ps:
            y, x, c = p
            if c == -1:
                continue
            dx, dy = dd[c]
            nx = x + dx; ny = y + dy
            if U[ny][nx] == -1:
                U[ny][nx] = 1
                if S[ny][nx] == 'X':
                    rest -= 1
                    p[2] = -1
                    qs.append((ny, nx))
                else:
                    p[0] = ny; p[1] = nx
                qs.append((y, x))
        for y, x in qs:
            U[y][x] = -1
        t += 1
    if t <= 180:
        print(t)
    else:
        print("NA")

Submission status: Accepted

Solution code:
while True:
  dic = {"#":-3, ".":-1, "X":-2, "E":0, "N":1, "W":2, "S":3}
  def fix(c):
    return dic[c]
  w, h = map(int, input().split())
  if w == 0:
    break
  mp = [list(map(fix, list(input()))) for _ in range(h)]
  
  persons = []
  for y in range(h):
    for x in range(w):
      if mp[y][x] in (0, 1, 2, 3):
        persons.append([x, y, mp[y][x]])
  
  vx = (1, 0, -1, 0)
  vy = (0, -1, 0, 1)
  
  time = 0
  while time < 180:
    if not persons:
      print(time)
      break
    reserve = {}
    for index, state in enumerate(persons):
      x, y, d = state
      for i in range(d - 1, d + 3):
        dx, dy = vx[i % 4], vy[i % 4]
        if mp[y + dy][x + dx] in (-1, -2):
          persons[index][2] = i % 4
          if (x + dx, y + dy) in reserve:
            if reserve[(x + dx, y + dy)][1] > (i + 2) % 4:
              reserve[(x + dx, y + dy)] = (index, (i + 2) % 4, mp[y + dy][x + dx])
          else:
            reserve[(x + dx, y + dy)] = (index, (i + 2) % 4, mp[y + dy][x + dx])
          break
    
    reserve = sorted(reserve.items(), key=lambda a:-a[1][0])
    for k, v in reserve:
      nx, ny = k
      index, nd, panel = v
      px, py, _ = persons[index]
      mp[py][px] = -1
      if panel == -1:
        persons[index] = [nx, ny, (nd + 2) % 4]
        mp[ny][nx] = (nd + 2) % 4
      else:
        persons.pop(index)
    
    time += 1
  
  else:
    print("NA")

Submission status: Accepted

Solution code:
from collections import defaultdict
from typing import Dict


class Players(object):
    def __init__(self):
        self.players: Dict[int, "Player"] = {}
        self.reservation = defaultdict(list)
        self.square = None
        self.goal = []

    def set_goal(self, x, y):
        self.goal.append((x, y))

    def add(self, player: "Player"):
        self.players[len(self.players)] = player

    def search_all(self):
        for i, player in self.players.items():
            x, y, d = player.search(self.square)
            self.reservation[(x, y)].append(((d-2)%4, i))
        for k, v in self.reservation.items():
            if len(v) == 1:
                continue
            self.reservation[k] = [min(v)]

    def move_all(self):
        for (x, y), l in self.reservation.items():
            _id = l[0][1]
            _x, _y = self.players[_id].pos
            self.players[_id].move(x, y)
            self.square[_y][_x], self.square[y][x] = ".", "o"

        self.reservation.clear()
        for i, player in self.players.copy().items():
            x, y = player.pos
            if (x, y) in self.goal:
                del self.players[i]
                self.square[y][x] = "."

    @property
    def is_finished(self):
        return len(self.players) == 0


class Player(object):
    dir_dict = {"E": 0, "N": 1, "W": 2, "S": 3}
    dir_diff = ((1, 0), (0, -1), (-1, 0), (0, 1))

    def __init__(self, x, y, direction):
        self.x = x
        self.y = y
        self.dir = self.dir_dict[direction]

    def search(self, square):
        for i in range(self.dir-1, self.dir+3):
            dx, dy = self.dir_diff[i % 4]
            if square[self.y+dy][self.x+dx] in (".", "X"):
                self.dir = i % 4
                return self.x+dx, self.y+dy, self.dir
        else:
            return self.x, self.y, self.dir

    def move(self, x, y):
        self.x, self.y = x, y

    @property
    def pos(self):
        return self.x, self.y


while True:
    W, H = map(int, input().split())
    if W == 0:
        break
    square = []
    players = Players()
    for y in range(H):
        square.append(list(input()))
        for x, c in enumerate(square[-1]):
            if c in "ENWS":
                players.add(Player(x, y, c))
            elif c == "X":
                players.set_goal(x, y)
    players.square = square

    for i in range(1, 121):
        players.search_all()
        players.move_all()
        if players.is_finished:
            print(i)
            break
    else:
        print("NA")

Submission status: Runtime Error

Solution code:
direction = {'N' : 0, 'E' : 1, 'S' : 2, 'W' : 3}
step = [(-1, 0), (0, 1), (1, 0), (0, -1)]

while True:
    W, H = map(int, raw_input().split())
    if W == 0 and H == 0: break
    m = [None] * H
    for i in xrange(H):
        m[i] = list(raw_input())
    people = []
    for i in xrange(H):
        for j in xrange(W):
            if m[i][j] in "NESW":
                people.append( (i, j, direction[m[i][j]]) )
    time = 0
    while any(people):
        time += 1
        if time > 180:
            time = -1
            break
        sched = []
        for n in xrange(len(people)):
            if people[n] is None: continue
            x, y, d = people[n]
            for i in range(1, -3, -1):
                    dx, dy = step[(d+i+4)%4]
                    if 0 <= x+dx < H and 0 <= y+dy < W and m[x + dx][y + dy] in "X.":
                        beat = True
                    for k in range(len(sched)):
                        xx, yy, dd = sched[k][1:]
                        if (x+dx, y+dy) == (xx, yy):
                            if dd%4 < (d+i+4)%4:
                                sched[k] = ( n, x+dx, y+dy, (d+i+4)%4 )
                                beat = False
                                break
                            else:
                                beat = False
                                break
                    if beat:
                        sched.append( ( n, x+dx, y+dy, (d+i+4)%4 ) )
                    break
        for (k, x, y, d) in sched:
            m[ people[k][0] ][ people[k][1] ] = '.'
            if m[x][y] == 'X':
                people[k] = None
            else:
                m[x][y] = 'H'
                people[k] = x, y, d
        for d in m:
            for c in d:
                print c,
            print ''
        print ''
    if time > 0:
        print time
    else:
        print 'NA'

Submission status: Runtime Error

Solution code:
direction = {'N' : 0, 'E' : 1, 'S' : 2, 'W' : 3}
step = [( -1, 0 ), ( 0, 1 ), ( 1, 0 ), ( 0, -1 )]

while True:
    W, H = map( int, raw_input().split() )
    if W == 0 and H == 0: break
    m = [ list( raw_input().split() ) for i in xrange( H ) ]
    people = [ ( i, j, direction[ m[i][j] ] ) for i in xrange( H ) for j in range( W )
               if m[i][j] in "NESW" ]
    time = 0
    while any( people ):
        time += 1
        if time > 180:
            time = -1
            break
        sched = []
        for n in xrange( len( people ) ):
            if people[n] is None: continue
            x, y, d = people[n]
            for i in range(1, -3, -1):
                    dx, dy = step[(d + i) % 4]
                    if 0 <= x+dx < H and 0 <= y+dy < W and m[x+dx][y+dy] in "X.":
                        beat = True
                        for k in range( len( sched ) ):
                            xx, yy, dd = sched[k][1:]
                            if ( x+dx, y+dy ) == ( xx, yy ):
                                if dd < (d + i) % 4:
                                    sched[k] = ( n, x+dx, y+dy, (d + i) % 4 )
                                    beat = False
                                    break
                                else:
                                    beat = False
                                    break
                        if beat:
                            sched.append( ( n, x+dx, y+dy, (d + i) % 4 ) )
			break
        for ( k, x, y, d ) in sched:
            m[ people[k][0] ][ people[k][1] ] = '.'
            if m[x][y] == 'X':
                people[k] = None
            else:
                m[x][y] = 'H'
                people[k] = x, y, d
    if time > 0:
        print time
    else:
        print 'NA'

Submission status: Runtime Error

Solution code:
import sys

direction = {'N' : 0, 'E' : 1, 'S' : 2, 'W' : 3}
step = [( -1, 0 ), ( 0, 1 ), ( 1, 0 ), ( 0, -1 )]
vv = []

while True:
    W, H = map( int, sys.stdin.readline().rstrip().split() )
    if W == 0 and H == 0: break
    m = [ list( sys.stdin.readline().strip() ) for i in xrange( H ) ]
    people = [ ( i, j, direction[ m[i][j] ] ) for i in xrange( H ) for j in range( W )
               if m[i][j] in "NESW" ]
    time = 0
    while any( people ):
        time += 1
        if time > 180:
            time = -1
            break
        sched = []
        for n in xrange( len( people ) ):
            if people[n] is None: continue
            x, y, d = people[n]
            for i in range(1, -3, -1):
                    dx, dy = step[(d + i) % 4]
                    if 0 <= x+dx < H and 0 <= y+dy < W and m[x+dx][y+dy] in "X.":
                        people[n][2] = (d + i) % 4
                        beat = True
                        for k in range( len( sched ) ):
                            xx, yy, dd = sched[k][1:]
                            if ( x+dx, y+dy ) == ( xx, yy ):
                                if dd < (d + i) % 4:
                                    sched[k] = ( n, x+dx, y+dy, (d + i) % 4 )
                                    beat = False
                                    break
                                else:
                                    beat = False
                                    break
                        if beat:
                            sched.append( ( n, x+dx, y+dy, (d + i) % 4 ) )
			break
        for ( k, x, y, d ) in sched:
            m[ people[k][0] ][ people[k][1] ] = '.'
            if m[x][y] == 'X':
                people[k] = None
            else:
                m[x][y] = 'H'
                people[k] = x, y, d
    if time >= 0:
        vv.append(time)
    else:
        vv.append('NA')

for v in vv:
    print v

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 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
                xs = ys
            else:
                ans.append("NA")
hinan()