結果
問題 | No.5015 Escape from Labyrinth |
ユーザー |
![]() |
提出日時 | 2023-04-16 07:27:27 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
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 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
import sysinput = sys.stdin.readlinefrom collections import dequeN,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=startD[x][y]=0Q=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]+1Q.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]+1Q.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]+1Q.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]+1Q.append((x,y+1))U[x][y+1]="R"x,y=keyANS=[]while [x,y]!=start:#print(x,y)if U[x][y]=="D":ANS.append("D")x-=1elif U[x][y]=="U":ANS.append("U")x+=1elif U[x][y]=="R":ANS.append("R")y-=1elif U[x][y]=="L":ANS.append("L")y+=1D=[[1<<30]*N for i in range(N)]U=[[""]*N for i in range(N)]x,y=keyD[x][y]=0Q=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]+1Q.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]+1Q.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]+1Q.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]+1Q.append((x,y+1))U[x][y+1]="R"x,y=goalANS2=[]while [x,y]!=key:#print(x,y)if U[x][y]=="D":ANS2.append("D")x-=1elif U[x][y]=="U":ANS2.append("U")x+=1elif U[x][y]=="R":ANS2.append("R")y-=1elif U[x][y]=="L":ANS2.append("L")y+=1LANS=ANS[::-1]+ANS2[::-1]for com in LANS:print("M",com)