Buggy python submission (verdict: Time Limit Exceeded):
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()


Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
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()


Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
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()


Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
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()


Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
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()


Fixed submission:
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()