Problem:


パチモンクリーチャー

 某国で大人気のゲーム、パチモンクリーチャーが日本でリメイクされて発売されました。 ゲームが大好きなあなたは、  このゲームを何度もプレイするうちにどうしたら最速でクリアできるのか考えるようになりました。しかし、いくら考えても最速の攻略方法がわからなかったあなたは、どれだけ早くゲームをクリアできるかを求めるプログラムを作成することにしました。 

ゲームの詳細は以下の通りです。

パチモンクリーチャー(以下、パチクリ)という生物が多く存在する世界がゲームの舞台です。各パチクリは、火属性、氷属性、木属性、土属性、水属性の 5 種類の属性のいずれか１つの属性を持ちます。ゲームの主人公は、ゲーム開始時に好きな属性のパチクリ一匹を冒険のパートナーとして選びます。そのパチクリと共にゴールを目指し、ゴールにいるライバルを倒してパチクリマスターになることがゲームの目的です。

 しかし、ライバルを倒すためには全属性のパチクリがいないと勝てないので、途中で全属性のパチクリを捕まえなければなりません。パチクリを捕まえるには属性がカギとなります。火属性のパチクリは氷属性のパチクリを捕まえることができ、同様に、氷属性は木属性、木属性は土属性、土属性は水属性、水属性は火属性を捕まえることができます。属性の関連は以下の図のようになります。

以下の図はゲームが行われるマップの一例を表しています。

 主人公はパチクリを一匹もってスタート地点である「S」から出発し、一マスずつ移動しながらゴール地点である「G」を目指します。その途中で、最初に持っているパチクリ以外の 4 つの属性のパチクリを捕まえ、ゴール地点であるマス目に移動するとゲーム終了となります。

主人公は、今いるマス目から、辺を共有する隣のマス目に移動することができ、それを一回の移動と数えます。主人公がパチクリのいるマスに移動した場合、そのパチクリを捕まえられる属性のパチクリを持っていればそのパチクリを捕まえたことになります。そのマスにいるパチクリを捕まえられるかの可否にかかわらず、すべてのマスに何度でも移動することができます。

 マップの大きさ(横方向の列数、縦方向の行数)とマップの初期状態を入力とし、初めに選んだパチクリの属性と、それ以外の 4 つの属性のパチクリを捕まえるのにかかる、スタート地点からゴール地点に至る最小移動数を出力するプログラムを作成してください。

Input

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

W H
c11c12...c1W
c21c22...c2W
:
cH1cH2...cHW

1 行目にマップの横方向の列数 W と縦方向の行数 H (2 ≤ W, H ≤ 1000) が与えられます。続く H 行にマップの i 行目の情報が与えられます。入力されるマップには各マスの状態が与えられます。     「S」は主人公のスタート地点を、  「G」はゴール地点を、「1」「2」「3」「4」「5」はそこにいるパチクリの属性を( 1:火属性、 2:氷属性、    3:木属性、 4:土属性、 5:水属性 をそれぞれ表します)、 「.(ピリオド) 」は何もないマスをそれぞれ表します。 
各属性のパチクリの数はそれぞれ 0 以上 1000 以下とします。

データセットの数は140 を超えません。また、データセットの 80 % について、W, H は100 を超えません。

Output

入力データセットごとに、最初に選んだパチクリの属性と最小移動数を１行に出力します。なお、どのように初めのパチクリを選んでも、どのような経路で移動してもそれら 4 つの属性のパチクリを捕まえることができない場合は NA と出力してください。  また、最小移動数が同じになるような最初のパチクリの選び方が複数ある場合は、属性の数字が小さいものを出力してください。

Sample Input

6 6
S.1..4
3..5..
..4.1.
4....5
.2.32.
5.1..G
3 2
...
S.G
0 0

Output for the Sample Input

2 10
NA



Sample input:
6 6
S.1..4
3..5..
..4.1.
4....5
.2.32.
5.1..G
3 2
...
S.G
0 0


Sample output:
2 10
NA

Submission status: Wrong Answer

Solution code:
from itertools import product
# from line_profiler import LineProfiler
def main():
    while(True):
        W, H = map(int,input().split())
        if not W: break
        # ma = [[-1]*(W+2) for _ in range(H+2)]
        ps = [[] for _ in range(5)]
        ans = 10**10
        for i in range(H):
            for j,a in enumerate(input()):
                if a == "S": ss = [[i,j]]
                elif a == "G": gg = [[i,j]]
                elif a != ".": ps[int(a)-1].append([i,j])
        # if [1 for i in range(5) if len(ps[i])==0]:
        #     print("NA"); continue
        # print(ps)
        B = float("inf")
        Bi = -1
        for mon1 in range(5):
            dp = [[float("inf")]*1000 for _ in range(5)]
            cand = [[0,ss[0][0],ss[0][1]]]
            for mon2 in range(5):
                dpCacheNow = dp[mon2]
                dpCacheNxt = dp[(mon1+mon2+1)%5]
                dpCacheNow[0] = 0
                nxt = ps[(mon1+mon2+1)%5] if mon2<4 else gg
                # print(nxt)
                # print(cand)
                tmp = []
                for i,[ty,tx] in enumerate(nxt):
                    # if dpCacheNow[i] >= B:
                    #     continue
                    tc = float("inf")
                    # for cc,cy,cx in cand:
                    for cc,cy,cx in cand:
                        if cc > B:
                            # print("a",end="")
                            tc = float("inf")
                            break
                        else:
                            tc = min(tc,abs(ty-cy)+abs(tx-cx)+cc)
                    tmp.append([tc,ty,tx])
                    dpCacheNxt[i] = min(dpCacheNxt[i],tc)
                cand = tmp
            if cand[0][0] < B:
                B = cand[0][0]
                Bi = mon1
        if(Bi == -1):
            print("NA")
        else:
            print("%d %d"%(Bi+1,B))
        # for mon1 in range(5):
        #     mon2 = (mon1+1)%5
        #     dp = [[10**10]*1000 for _ in range(5)]
        #     for i,yx in enumerate(ps[mon2]):
        #         dp[mon2][i] = abs(ss[0]-yx[0])+abs(ss[1]-yx[1])
        #     mon3 = mon2
        #     for mon3 in range(mon2,mon2+3):
        #         mon3 = mon3%5
        #         mon4 = (mon3+1)%5
        #         for [i,yx],[j,nyx] in product(enumerate(ps[mon3]),enumerate(ps[mon4])):
        #             dp[mon4][j] = min(dp[mon4][j],dp[mon3][i]+abs(yx[0]-nyx[0])+abs(yx[1]-nyx[1]))
        #     mon5 = (mon1-1)%5
        #     for i,yx in enumerate(ps[mon5]):
        #         d = dp[mon5][i] + abs(gg[0]-yx[0])+abs(gg[1]-yx[1])
        #         if ans > d:
        #             ans,ansi = d,mon1
        # print(ansi+1,ans)

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
# from line_profiler import LineProfiler
def main():
    while(True):
        W, H = map(int,input().split())
        if not W: break
        # ma = [[-1]*(W+2) for _ in range(H+2)]
        ps = [[] for _ in range(5)]
        ans = 10**10
        for i in range(H):
            for j,a in enumerate(input()):
                if a == "S": ss = [i,j]
                elif a == "G": gg = [i,j]
                elif a != ".": ps[int(a)-1].append([i,j])
        if [1 for i in range(5) if len(ps[i])==0]:
            print("NA"); continue
        for mon1 in range(5):
            mon2 = (mon1+1)%5
            dp = [[10**10]*1000 for _ in range(5)]
            for i,yx in enumerate(ps[mon2]):
                dp[mon2][i] = abs(ss[0]-yx[0])+abs(ss[1]-yx[1])
            mon3 = mon2
            for mon3 in range(mon2,mon2+3):
                mon3 = mon3%5
                mon4 = (mon3+1)%5
                for [i,yx],[j,nyx] in product(enumerate(ps[mon3]),enumerate(ps[mon4])):
                    dp[mon4][j] = min(dp[mon4][j],dp[mon3][i]+abs(yx[0]-nyx[0])+abs(yx[1]-nyx[1]))
            mon5 = (mon1-1)%5
            for i,yx in enumerate(ps[mon5]):
                d = dp[mon5][i] + abs(gg[0]-yx[0])+abs(gg[1]-yx[1])
                if ans > d:
                    ans,ansi = d,mon1
        print(ansi+1,ans)

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
# from line_profiler import LineProfiler
def main():
    while(True):
        W, H = map(int,input().split())
        if not W: break
        # ma = [[-1]*(W+2) for _ in range(H+2)]
        ps = [[] for _ in range(5)]
        ans = 10**10
        for i in range(H):
            for j,a in enumerate(input()):
                if a == "S": ss = [[i,j]]
                elif a == "G": gg = [[i,j]]
                elif a != ".": ps[int(a)-1].append([i,j])
        # if [1 for i in range(5) if len(ps[i])==0]:
        #     print("NA"); continue
        # print(ps)
        B = float("inf")
        Bi = -1
        for mon1 in range(5):
            cand = [[0,ss[0][0],ss[0][1]]]
            for mon2 in range(5):
                nxt = ps[(mon1+mon2+1)%5] if mon2<4 else gg
                # print(nxt)
                # print(cand)
                tmp = []
                for ty,tx in nxt:
                    tc = float("inf")
                    for cc,cy,cx in cand:
                        tc = min(tc,abs(ty-cy)+abs(tx-cx)+cc)
                    tmp.append([tc,ty,tx])
                cand = tmp
            if cand[0][0] < B:
                B = cand[0][0]
                Bi = mon1
        if(Bi == -1):
            print("NA")
        else:
            print("%d %d"%(Bi+1,B))
        # for mon1 in range(5):
        #     mon2 = (mon1+1)%5
        #     dp = [[10**10]*1000 for _ in range(5)]
        #     for i,yx in enumerate(ps[mon2]):
        #         dp[mon2][i] = abs(ss[0]-yx[0])+abs(ss[1]-yx[1])
        #     mon3 = mon2
        #     for mon3 in range(mon2,mon2+3):
        #         mon3 = mon3%5
        #         mon4 = (mon3+1)%5
        #         for [i,yx],[j,nyx] in product(enumerate(ps[mon3]),enumerate(ps[mon4])):
        #             dp[mon4][j] = min(dp[mon4][j],dp[mon3][i]+abs(yx[0]-nyx[0])+abs(yx[1]-nyx[1]))
        #     mon5 = (mon1-1)%5
        #     for i,yx in enumerate(ps[mon5]):
        #         d = dp[mon5][i] + abs(gg[0]-yx[0])+abs(gg[1]-yx[1])
        #         if ans > d:
        #             ans,ansi = d,mon1
        # print(ansi+1,ans)

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
# from line_profiler import LineProfiler
def main():
    while(True):
        W, H = map(int,input().split())
        if not W: break
        # ma = [[-1]*(W+2) for _ in range(H+2)]
        ps = [[] for _ in range(5)]
        ans = 10**10
        for i in range(H):
            for j,a in enumerate(input()):
                if a == "S": ss = [[i,j]]
                elif a == "G": gg = [[i,j]]
                elif a != ".": ps[int(a)-1].append([i,j])
        # if [1 for i in range(5) if len(ps[i])==0]:
        #     print("NA"); continue
        # print(ps)
        B = float("inf")
        Bi = -1
        for mon1 in range(5):
            cand = [[0,ss[0][0],ss[0][1]]]
            for mon2 in range(5):
                nxt = ps[(mon1+mon2+1)%5] if mon2<4 else gg
                # print(nxt)
                # print(cand)
                tmp = []
                for ty,tx in nxt:
                    tc = float("inf")
                    # for cc,cy,cx in cand:
                    if cand:
                        tc = min([abs(ty-cy)+abs(tx-cx)+cc for cc,cy,cx in cand])
                    tmp.append([tc,ty,tx])
                cand = tmp
            if cand[0][0] < B:
                B = cand[0][0]
                Bi = mon1
        if(Bi == -1):
            print("NA")
        else:
            print("%d %d"%(Bi+1,B))
        # for mon1 in range(5):
        #     mon2 = (mon1+1)%5
        #     dp = [[10**10]*1000 for _ in range(5)]
        #     for i,yx in enumerate(ps[mon2]):
        #         dp[mon2][i] = abs(ss[0]-yx[0])+abs(ss[1]-yx[1])
        #     mon3 = mon2
        #     for mon3 in range(mon2,mon2+3):
        #         mon3 = mon3%5
        #         mon4 = (mon3+1)%5
        #         for [i,yx],[j,nyx] in product(enumerate(ps[mon3]),enumerate(ps[mon4])):
        #             dp[mon4][j] = min(dp[mon4][j],dp[mon3][i]+abs(yx[0]-nyx[0])+abs(yx[1]-nyx[1]))
        #     mon5 = (mon1-1)%5
        #     for i,yx in enumerate(ps[mon5]):
        #         d = dp[mon5][i] + abs(gg[0]-yx[0])+abs(gg[1]-yx[1])
        #         if ans > d:
        #             ans,ansi = d,mon1
        # print(ansi+1,ans)

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
# from line_profiler import LineProfiler
def main():
    while(True):
        W, H = map(int,input().split())
        if not W: break
        # ma = [[-1]*(W+2) for _ in range(H+2)]
        ps = [[] for _ in range(5)]
        ans = 10**10
        for i in range(H):
            for j,a in enumerate(input()):
                if a == "S": ss = [i,j]
                elif a == "G": gg = [i,j]
                elif a != ".": ps[int(a)-1].append([i,j])
        # if [1 for i in range(5) if len(ps[i])==0]:
        #     print("NA"); continue
        # print(ps)
        B = float("inf")
        Bi = -1
        for mon1 in range(5):
            dp = [[float("inf")]*1000 for _ in range(5)]
            # cand = [[0,ss[0][0],ss[0][1]]]
            now = (mon1+1)%5
            dpCacheNow = dp[now]
            emCacheNow = ps[now]
            for i,[ty,tx] in enumerate(emCacheNow):
                dpCacheNow[i] = abs(ss[0]-ty) + abs(ss[1]-tx)
            for e in range(3):
                nxt = (now+1)%5
                dpCacheNxt = dp[nxt]
                emCacheNxt = ps[nxt]
                for i,[nowy,nowx] in enumerate(emCacheNow):
                    if dpCacheNow[i] > B: continue
                    for j,[nxty,nxtx] in enumerate(emCacheNxt):
                        dpCacheNxt[j] = min(dpCacheNxt[j],dpCacheNow[i]+abs(nowy-nxty)+abs(nowx-nxtx))
                now = nxt
                dpCacheNow = dpCacheNxt
                emCacheNow = emCacheNxt
            for i,[ey,ex] in enumerate(emCacheNxt):
                tmp = dpCacheNxt[i] + abs(gg[0]-ey) + abs(gg[1]-ex)
                if tmp < B:
                    B = tmp
                    Bi = mon1
            # for mon2 in range(5):
            #     # dpCacheNow = dp[mon2]
            #     # dpCacheNxt = dp[(mon1+mon2+1)%5]
            #     # dpCacheNow[0] = 0
            #     nxt = ps[(mon1+mon2+1)%5] if mon2<4 else gg
            #     # print(nxt)
            #     # print(cand)
            #     tmp = []
            #     for i,[ty,tx] in enumerate(nxt):
            #         # if dpCacheNow[i] >= B:
            #         #     continue
            #         tc = float("inf")
            #         # for cc,cy,cx in cand:
            #         for cc,cy,cx in cand:
            #             # if cc > B:
            #             #     # print("a",end="")
            #             #     tc = float("inf")
            #             #     break
            #             # else:
            #             tc = min(tc,abs(ty-cy)+abs(tx-cx)+cc)
            #             tc
            #         tmp.append([tc,ty,tx])
            #         # dpCacheNxt[i] = min(dpCacheNxt[i],tc)
            #     cand = tmp
            # if cand[0][0] < B:
            #     B = cand[0][0]
            #     Bi = mon1
        if(Bi == -1):
            print("NA")
        else:
            print("%d %d"%(Bi+1,B))
        # for mon1 in range(5):
        #     mon2 = (mon1+1)%5
        #     dp = [[10**10]*1000 for _ in range(5)]
        #     for i,yx in enumerate(ps[mon2]):
        #         dp[mon2][i] = abs(ss[0]-yx[0])+abs(ss[1]-yx[1])
        #     mon3 = mon2
        #     for mon3 in range(mon2,mon2+3):
        #         mon3 = mon3%5
        #         mon4 = (mon3+1)%5
        #         for [i,yx],[j,nyx] in product(enumerate(ps[mon3]),enumerate(ps[mon4])):
        #             dp[mon4][j] = min(dp[mon4][j],dp[mon3][i]+abs(yx[0]-nyx[0])+abs(yx[1]-nyx[1]))
        #     mon5 = (mon1-1)%5
        #     for i,yx in enumerate(ps[mon5]):
        #         d = dp[mon5][i] + abs(gg[0]-yx[0])+abs(gg[1]-yx[1])
        #         if ans > d:
        #             ans,ansi = d,mon1
        # print(ansi+1,ans)

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

Submission status: Time Limit Exceeded

Solution code:
def distance(a, b):
    return abs(a[0]-b[0]) + abs(a[1]-b[1])
while True:
    w, h = map(int, raw_input().split())
    if w==0 and h==0: break
    f = [[] for i in range(5)]
    memo = [[0 for i in range(5)] for j in range(1000)]
    for i in range(h):
        a = raw_input()
        for j in range(w):
            if a[j] == "S": s = [i,j]
            elif a[j] == "G": g = [i,j]
            elif a[j] == "1": f[int(a[j])-1].append([i,j])
            elif a[j] == "2": f[int(a[j])-1].append([i,j])
            elif a[j] == "3": f[int(a[j])-1].append([i,j])
            elif a[j] == "4": f[int(a[j])-1].append([i,j])
            elif a[j] == "5": f[int(a[j])-1].append([i,j])
    ans = 1 << 30
    for i in range(5):
        pre = i; next = (i+1) % 5;
        for j in range(len(f[next])):
            print j, next
            memo[j][next] = distance(s,f[next][j])
        pre = next; next = (next+1) % 5;
        for j in range(3):
            for k in range(len(f[next])):
                memo[k][next] = 1 << 30
                for l in range(len(f[pre])):
                    memo[k][next] = min(memo[k][next], memo[l][pre]+distance(f[pre][l],f[next][k]))
            pre = next; next = (next+1) % 5;
        for j in range(len(f[pre])):
            tmp = memo[j][pre]+distance(f[pre][j], g)
            if tmp < ans:
                ans = tmp
                ret = i
    if ans == 1 << 30: print "NA"
    else: print ret+1, ans

Submission status: Time Limit Exceeded

Solution code:
def distance(a, b):
    return abs(a[0]-b[0]) + abs(a[1]-b[1])
while True:
    w, h = map(int, raw_input().split())
    if w==0 and h==0: break
    f = [[] for i in range(5)]
    memo = [[0 for i in range(5)] for j in range(1000)]
    for i in range(h):
        a = raw_input()
        for j in range(w):
            if a[j] == "S": s = [i,j]
            elif a[j] == "G": g = [i,j]
            elif a[j] == "1": f[int(a[j])-1].append([i,j])
            elif a[j] == "2": f[int(a[j])-1].append([i,j])
            elif a[j] == "3": f[int(a[j])-1].append([i,j])
            elif a[j] == "4": f[int(a[j])-1].append([i,j])
            elif a[j] == "5": f[int(a[j])-1].append([i,j])
    ans = 1 << 30
    for i in range(5):
        pre = i; next = (i+1) % 5;
        for j in range(len(f[next])):
            memo[j][next] = distance(s,f[next][j])
        pre = next; next = (next+1) % 5;
        for j in range(3):
            for k in range(len(f[next])):
                memo[k][next] = 1 << 30
                for l in range(len(f[pre])):
                    memo[k][next] = min(memo[k][next], memo[l][pre]+distance(f[pre][l],f[next][k]))
            pre = next; next = (next+1) % 5;
        for j in range(len(f[pre])):
            tmp = memo[j][pre]+distance(f[pre][j], g)
            if tmp < ans:
                ans = tmp
                ret = i
    if ans == 1 << 30: print "NA"
    else: print ret+1, ans

Submission status: Time Limit Exceeded

Solution code:
def distance(a, b):
    return abs(a[0]-b[0]) + abs(a[1]-b[1])
while True:
    w, h = map(int, raw_input().split())
    if w==0 and h==0: break
    f = [[] for r in range(5)]
    memo = [[1<<30 for c in range(5)] for r in range(1000)]
    for i in range(h):
        a = raw_input()
        for j in range(w):
            if a[j] == "S": s = (i,j)
            elif a[j] == "G": g = (i,j)
            elif a[j] == "1": f[int(a[j])-1].append((i,j))
            elif a[j] == "2": f[int(a[j])-1].append((i,j))
            elif a[j] == "3": f[int(a[j])-1].append((i,j))
            elif a[j] == "4": f[int(a[j])-1].append((i,j))
            elif a[j] == "5": f[int(a[j])-1].append((i,j))
    ans = 1<<30
    for i in range(5):
        pre = i; cur = (i+1) % 5;
        for j in range(len(f[cur])):
            memo[j][cur] = distance(s,f[cur][j])
        pre = cur; cur = (cur+1) % 5;
        for j in range(3):
            for k in range(len(f[cur])):
                for l in range(len(f[pre])):
                    memo[k][cur] = min(memo[k][cur], memo[l][pre]+distance(f[pre][l],f[cur][k]))
            pre = cur; cur = (cur+1) % 5;
        for j in range(len(f[pre])):
            tmp = memo[j][pre]+distance(f[pre][j], g)
            if tmp < ans:
                ans = tmp
                ret = i
    if ans == 1<<30: print "NA"
    else: print ret+1, ans

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
# from line_profiler import LineProfiler
def main():
    while(True):
        W, H = map(int,input().split())
        if not W: break
        B = float('inf')
        Bi = -1
        consequNodes = []
        monsterNodes = [[] for _ in range(5)]
        idx = 0
        for i in range(H):
            for j,a in enumerate(input()):
                if a == ".":
                    continue
                elif a == "S": 
                    consequNodes.append([i,j,idx,5])
                    startNode = [i,j,idx,5]
                    idx+=1
                elif a == "G":
                    consequNodes.append([i,j,idx,6])
                    goalNode = [i,j,idx,6]
                    idx+=1
                elif a != ".":
                    consequNodes.append([i,j,idx,int(a)-1])
                    monsterNodes[int(a)-1].append([i,j,idx])
                    idx+=1
        for z in range(5):
            consequNodes[startNode[2]][3] = z
            dist = [[float('inf')]*idx for _ in range(6)]
            dist[1][startNode[2]] = 0
            que = [(0,1,startNode[2],0)]
            reached = False
            while que:
                cst,numrep,nid,huristicCost = heappop(que)
                cst = int(cst)-int(huristicCost)
                if numrep == 5:
                    reached = True
                    cst += abs(consequNodes[nid][0]-goalNode[0]) + abs(consequNodes[nid][1]-goalNode[1])
                    break
                nxtmonster = (consequNodes[nid][3]+1)%5
                for nxty,nxtx,nxtid in monsterNodes[nxtmonster]:
                    tmpCost = dist[numrep][nid] + abs(nxty-consequNodes[nid][0]) + abs(nxtx-consequNodes[nid][1])
                    if tmpCost < dist[numrep+1][nxtid]:
                        dist[numrep+1][nxtid] = tmpCost
                        h = abs(nxty-goalNode[0]) + abs(nxtx-goalNode[1])
                        h *= 0.99
                        heappush(que,(tmpCost+h,numrep+1,nxtid,h))
            if reached and cst < B:
                B = cst
                Bi = z+1
        if Bi == -1:
            print("NA")
        else:
            print(Bi,B)

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

Submission status: Runtime Error

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


from itertools import product
from collections import defaultdict
from collections import namedtuple
from operator import itemgetter
from math import isinf
Point = namedtuple('Point', 'x y')

def distance(a, b):
    return abs(a.x - b.x) + abs(a.y - b.y)

def solve(route, location):
    dp = {}
    for ri in route:
        dp[ri] = [float('inf')] * len(location[ri])
    dp['S'][0] = 0
    for i in range(len(route) - 1):
        s, t = route[i], route[i + 1]
        for si, tj in product(range(len(location[s])), range(len(location[t]))):
            d = distance(location[s][si], location[t][tj])
            if dp[t][tj] > dp[s][si] + d:
                dp[t][tj] = dp[s][si] + d
    return dp['G'][0]

def main():
    while True:
        w, h = map(int, readline().split())
        if w == 0:
            break
        field = [readline().strip() for _ in range(h)]
        location = defaultdict(list)
        for y, x in product(range(h), range(w)):
            if field[y][x] != '.':
                location[field[y][x]].append(Point(x, y))
        element_route = [(i,'S' + ('12345' * 2)[i:i + 4] + 'G') for i in range(1, 6)]
        element_move = [(ei, solve(ri, location)) for ei, ri in element_route]
        ans = min(element_move, key=itemgetter(1, 0))
        print('NA' if isinf(ans[1]) else ' '.join(map(str, ans)))

main()