#860104 (Python3) No.5015 Escape from Labyrinth

• 問題: No.5015 Escape from Labyrinth
• ユーザー: titia
• 提出日時: 2023-04-16 07:27:27
• 言語: Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
• 結果: AC
• 実行時間: 52 ms / 3,000 ms
• コード長: 2,624 bytes
• コンパイル時間: 252 ms
• コンパイル使用メモリ: 11,096 KB
• 実行使用メモリ: 9,216 KB
• スコア: 12,250
• 最終ジャッジ日時: 2023-04-16 07:27:36
• 合計ジャッジ時間: 8,816 ms
• ジャッジサーバーID （参考情報）: judge11 / judge16

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	35 ms; 9,052 KB
testcase_01	AC	35 ms; 9,040 KB
testcase_02	AC	35 ms; 9,192 KB
testcase_03	AC	34 ms; 9,128 KB
testcase_04	AC	34 ms; 9,016 KB
testcase_05	AC	35 ms; 9,020 KB
testcase_06	AC	34 ms; 9,040 KB
testcase_07	AC	35 ms; 9,156 KB
testcase_08	AC	35 ms; 9,024 KB
testcase_09	AC	34 ms; 9,204 KB
testcase_10	AC	35 ms; 9,204 KB
testcase_11	AC	34 ms; 9,044 KB
testcase_12	AC	33 ms; 9,196 KB
testcase_13	AC	34 ms; 9,152 KB
testcase_14	AC	36 ms; 9,168 KB
testcase_15	AC	34 ms; 9,112 KB
testcase_16	AC	35 ms; 9,144 KB
testcase_17	AC	35 ms; 9,152 KB
testcase_18	AC	33 ms; 9,020 KB
testcase_19	AC	35 ms; 9,012 KB
testcase_20	AC	34 ms; 9,188 KB
testcase_21	AC	35 ms; 9,036 KB
testcase_22	AC	34 ms; 9,216 KB
testcase_23	AC	34 ms; 9,028 KB
testcase_24	AC	37 ms; 9,032 KB
testcase_25	AC	36 ms; 9,044 KB
testcase_26	AC	35 ms; 9,140 KB
testcase_27	AC	34 ms; 8,972 KB
testcase_28	AC	35 ms; 9,096 KB
testcase_29	AC	34 ms; 9,028 KB
testcase_30	AC	35 ms; 8,968 KB
testcase_31	AC	34 ms; 9,200 KB
testcase_32	AC	34 ms; 9,180 KB
testcase_33	AC	34 ms; 9,188 KB
testcase_34	AC	34 ms; 9,200 KB
testcase_35	AC	35 ms; 9,128 KB
testcase_36	AC	35 ms; 9,180 KB
testcase_37	AC	34 ms; 9,196 KB
testcase_38	AC	34 ms; 9,176 KB
testcase_39	AC	35 ms; 9,140 KB
testcase_40	AC	52 ms; 9,012 KB
testcase_41	AC	34 ms; 9,124 KB
testcase_42	AC	35 ms; 9,192 KB
testcase_43	AC	34 ms; 8,964 KB
testcase_44	AC	35 ms; 9,012 KB
testcase_45	AC	35 ms; 9,144 KB
testcase_46	AC	35 ms; 9,040 KB
testcase_47	AC	34 ms; 9,152 KB
testcase_48	AC	34 ms; 9,148 KB
testcase_49	AC	35 ms; 9,180 KB
testcase_50	AC	35 ms; 9,200 KB
testcase_51	AC	34 ms; 9,016 KB
testcase_52	AC	34 ms; 9,144 KB
testcase_53	AC	35 ms; 9,016 KB
testcase_54	AC	34 ms; 9,000 KB
testcase_55	AC	35 ms; 9,120 KB
testcase_56	AC	35 ms; 9,204 KB
testcase_57	AC	34 ms; 9,132 KB
testcase_58	AC	34 ms; 9,216 KB
testcase_59	AC	34 ms; 9,200 KB
testcase_60	AC	35 ms; 9,036 KB
testcase_61	AC	34 ms; 9,200 KB
testcase_62	AC	34 ms; 9,152 KB
testcase_63	AC	35 ms; 9,152 KB
testcase_64	AC	34 ms; 9,156 KB
testcase_65	AC	35 ms; 9,028 KB
testcase_66	AC	35 ms; 8,968 KB
testcase_67	AC	35 ms; 9,132 KB
testcase_68	AC	35 ms; 9,140 KB
testcase_69	AC	34 ms; 9,196 KB
testcase_70	AC	34 ms; 9,060 KB
testcase_71	AC	35 ms; 9,200 KB
testcase_72	AC	34 ms; 9,116 KB
testcase_73	AC	34 ms; 9,152 KB
testcase_74	AC	35 ms; 9,196 KB
testcase_75	AC	35 ms; 9,124 KB
testcase_76	AC	35 ms; 8,972 KB
testcase_77	AC	34 ms; 9,200 KB
testcase_78	AC	35 ms; 9,132 KB
testcase_79	AC	35 ms; 9,144 KB
testcase_80	AC	34 ms; 9,056 KB
testcase_81	AC	35 ms; 9,036 KB
testcase_82	AC	34 ms; 9,208 KB
testcase_83	AC	35 ms; 9,044 KB
testcase_84	AC	35 ms; 9,140 KB
testcase_85	AC	35 ms; 9,012 KB
testcase_86	AC	35 ms; 9,040 KB
testcase_87	AC	34 ms; 9,144 KB
testcase_88	AC	35 ms; 9,168 KB
testcase_89	AC	35 ms; 9,008 KB
testcase_90	AC	35 ms; 9,200 KB
testcase_91	AC	35 ms; 9,100 KB
testcase_92	AC	35 ms; 9,020 KB
testcase_93	AC	35 ms; 9,176 KB
testcase_94	AC	35 ms; 9,096 KB
testcase_95	AC	34 ms; 9,060 KB
testcase_96	AC	35 ms; 9,104 KB
testcase_97	AC	34 ms; 9,152 KB
testcase_98	AC	34 ms; 9,192 KB
testcase_99	AC	34 ms; 9,140 KB

ソースコード

import sys
input = sys.stdin.readline
from collections import deque

N,D,H=map(int,input().split())
MAP=[]
for i in range(N):
    S=input().strip()
    MAP.append(S)
M=int(input())
T=[list(map(int,input().split())) for i in range(M)]

for i in range(N):
    for j in range(N):
        if MAP[i][j]=="S":
            start=[i,j]
        elif MAP[i][j]=="G":
            goal=[i,j]
        elif MAP[i][j]=="K":
            key=[i,j]

D=[[1<<30]*N for i in range(N)]
U=[[""]*N for i in range(N)]
x,y=start
D[x][y]=0

Q=deque()
Q.append((x,y))
while Q:
    x,y=Q.popleft()

    if x-1>=0 and MAP[x-1][y]!="#" and MAP[x-1][y]!="E"  and D[x-1][y]>D[x][y]+1:
        D[x-1][y]=D[x][y]+1
        Q.append((x-1,y))
        U[x-1][y]="U"

    if x+1<N and MAP[x+1][y]!="#" and MAP[x+1][y]!="E"   and D[x+1][y]>D[x][y]+1:
        D[x+1][y]=D[x][y]+1
        Q.append((x+1,y))
        U[x+1][y]="D"

    if y-1>=0 and MAP[x][y-1]!="#" and MAP[x][y-1]!="E"   and D[x][y-1]>D[x][y]+1:
        D[x][y-1]=D[x][y]+1
        Q.append((x,y-1))
        U[x][y-1]="L"

    if y+1<N and MAP[x][y+1]!="#" and MAP[x][y+1]!="E"   and D[x][y+1]>D[x][y]+1:
        D[x][y+1]=D[x][y]+1
        Q.append((x,y+1))
        U[x][y+1]="R"

x,y=key
ANS=[]
while [x,y]!=start:
    #print(x,y)
    if U[x][y]=="D":
        ANS.append("D")
        x-=1
    elif U[x][y]=="U":
        ANS.append("U")
        x+=1
    elif U[x][y]=="R":
        ANS.append("R")
        y-=1
    elif U[x][y]=="L":
        ANS.append("L")
        y+=1



D=[[1<<30]*N for i in range(N)]
U=[[""]*N for i in range(N)]
x,y=key
D[x][y]=0

Q=deque()
Q.append((x,y))
while Q:
    x,y=Q.popleft()

    if x-1>=0 and MAP[x-1][y]!="#" and MAP[x-1][y]!="E" and D[x-1][y]>D[x][y]+1:
        D[x-1][y]=D[x][y]+1
        Q.append((x-1,y))
        U[x-1][y]="U"

    if x+1<N and MAP[x+1][y]!="#" and MAP[x+1][y]!="E"  and D[x+1][y]>D[x][y]+1:
        D[x+1][y]=D[x][y]+1
        Q.append((x+1,y))
        U[x+1][y]="D"

    if y-1>=0 and MAP[x][y-1]!="#" and MAP[x][y-1]!="E"  and D[x][y-1]>D[x][y]+1:
        D[x][y-1]=D[x][y]+1
        Q.append((x,y-1))
        U[x][y-1]="L"

    if y+1<N and MAP[x][y+1]!="#" and MAP[x][y+1]!="E"  and D[x][y+1]>D[x][y]+1:
        D[x][y+1]=D[x][y]+1
        Q.append((x,y+1))
        U[x][y+1]="R"

x,y=goal
ANS2=[]
while [x,y]!=key:
    #print(x,y)
    if U[x][y]=="D":
        ANS2.append("D")
        x-=1
    elif U[x][y]=="U":
        ANS2.append("U")
        x+=1
    elif U[x][y]=="R":
        ANS2.append("R")
        y-=1
    elif U[x][y]=="L":
        ANS2.append("L")
        y+=1

LANS=ANS[::-1]+ANS2[::-1]
for com in LANS:
    print("M",com)