結果

問題 No.5015 Escape from Labyrinth
コンテスト
ユーザー nikoro256
提出日時 2023-04-15 20:02:47
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,138 bytes
コンパイル時間 932 ms
コンパイル使用メモリ 87,188 KB
実行使用メモリ 82,208 KB
スコア 0
最終ジャッジ日時 2023-04-15 20:03:13
合計ジャッジ時間 21,769 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 6 RE * 69 TLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

def firstsolve():
    re=[]
    point=BFS(St,K)
    for b in BFS_Restoration(K,point)[::-1]:
        re.append(b)
    point=BFS(K,G)
    for b in BFS_Restoration(G,point)[::-1]:
        re.append(b)
    return re
    
def BFS_Restoration(end,point):
    thispoint=point[end[0]*N+end[1]]
    pos=end
    re=[pos]
    while thispoint!=0:
        for d in [[1,0],[-1,0],[0,1],[0,-1]]:
            x=pos[0]+d[0]
            y=pos[1]+d[1]
            if 0<x<=N and 0<=y<N and point[x*N+y]==thispoint-1:
                re.append((x,y))
                thispoint=point[x*N+y]
                pos=(x,y)
                break
    return re

def BFS(pos,end):
    point=[-1 for _ in range(N*N)]
    dq=deque()
    dq.append(pos)
    while len(dq)!=0:
        p=dq.popleft()
        if p==end:
            break
        for d in [[1,0],[-1,0],[0,1],[0,-1]]:
            x=p[0]+d[0]
            y=p[1]+d[1]
            if 0<x<=N and 0<=y<N and S[x][y]!='#' and S[x][y]!='E' and point[x*N+y]==-1:
                dq.append((x,y))
                point[x*N+y]=point[p[0]*N+p[1]]+1
    return point

def changetoans(way):
    pos=St
    ans=[]
    for w in way:
        d=[[1,0],[-1,0],[0,1],[0,-1]]
        change=[w[0]-pos[0],w[1]-pos[1]]
        for i in range(4):
            if change==d[i]:
                break
        ans_d=[]
        if 0<=i<=3:
            ans_d.append('M')
        if i==0:
            ans_d.append('D')
        elif i==1:
            ans_d.append('U')
        elif i==2:
            ans_d.append('R')
        elif i==3:
            ans_d.append('L')
        ans.append(ans_d)
        pos=w
    return ans

import sys
from collections import deque
input=sys.stdin.readline
N,D,H=map(int,input().split())
S=[]
St,G,K=(),(),()
for i in range(N):
    S.append(input())
    for j in range(N):
        if S[i][j]=='S':
            St=(i,j)
        elif S[i][j]=='G':
            G=(i,j)
        elif S[i][j]=='K':
            K=(i,j)
M=int(input())
dic={}
for _ in range(M):
    y,x,d=map(int,input().split())
    dic[(y,x)]=d
way=firstsolve()
print((St,K,G))
print(way)
ans=changetoans(way)
for a in ans:
    print(' '.join(a))
0