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: Wrong Answer

Solution code:
from sys import stdin
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
    # 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]])
        # print(dest)
        dest = sorted(dest,key=lambda x: (x[2:],x[1]))
        # for mmm in mt:
        #     print(mmm)
        # print("ps = ",ps,dest)
        dellist = []
        for pi,d,dy,dx in dest:
            if not mt[dy][dx]:
                mt[dy][dx] |= 1
                ps[pi][:2] = [dy,dx]
            if m[dy][dx] & 16:
                # print("OUT")
                # print(ttt)
                # time.sleep(3)
                dellist.append(pi)
        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: Wrong Answer

Solution code:
from sys import stdin
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 == 1 or H == 1:
        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]])
        # print(dest)
        dest = sorted(dest,key=lambda x: (x[2:],x[1]))
        # 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]:
                mt[dy][dx] |= 1
                ps[pi][:2] = [dy,dx]
            if m[dy][dx] & 16:
                # print("OUT")
                # print(ttt)
                # time.sleep(3)
                dellist.append(pi)
        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: Wrong Answer

Solution code:
from sys import stdin
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
    # 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]])
        # print(dest)
        dest = sorted(dest,key=lambda x: (x[2:],x[1]))
        # 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]:
                mt[dy][dx] |= 1
                ps[pi][:2] = [dy,dx]
            if m[dy][dx] & 16:
                # print("OUT")
                # print(ttt)
                # time.sleep(3)
                dellist.append(pi)
        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: Wrong Answer

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]])
        # print(dest)
        dest = sorted(dest,key=lambda x: (x[2:],x[1]))
        # 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]:
                mt[dy][dx] |= 1
                ps[pi][:2] = [dy,dx]
            if m[dy][dx] & 16:
                # print("OUT")
                # print(ttt)
                # time.sleep(3)
                dellist.append(pi)
        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: Wrong Answer

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 time <= 180 and any(people):
        time += 1
        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
    if time <= 180:
        print time
    else:
        print 'NA'

Submission status: Wrong Answer

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: Wrong Answer

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: Wrong Answer

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: Wrong Answer

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 = []
    for i in xrange( H ):
        m.append( 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 < (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
    if time > 0:
        print time
    else:
        print 'NA'

Submission status: Wrong Answer

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().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.":
                        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: Wrong Answer

Solution code:
import sys

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

while True:
    W, H = map( int, sys.stdin.readline().strip().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.":
                        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: Wrong Answer

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.":
                        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: Wrong Answer

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.":
                        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