Submission #2997391


Source Code Expand

Copy
import sys
from heapq import heappop,heappush
N,M,K=map(int,input().split())
D=input()
S=[]
for j in range(N):
    s=input()
    for i in range(M):
        if s[i]=='S':
            sx=i
            sy=j
        if s[i]=='G':
            gx=i
            gy=j
    S.append(s)
#LDRU->0123
inf=10**15
ds=[[inf]*(2*K+1) for i in range(4)]
for i in range(2*K-1,-1,-1):
    t=i%K
    if D[t]=='L':
        ds[0][i]=1
        ds[1][i]=ds[1][i+1]+1
        ds[2][i]=ds[2][i+1]+1
        ds[3][i]=ds[3][i+1]+1
    elif D[t]=='D':
        ds[0][i]=ds[0][i+1]+1
        ds[1][i]=1
        ds[2][i]=ds[2][i+1]+1
        ds[3][i]=ds[3][i+1]+1
    elif D[t]=='R':
        ds[0][i]=ds[0][i+1]+1
        ds[1][i]=ds[1][i+1]+1
        ds[2][i]=1
        ds[3][i]=ds[3][i+1]+1
    elif D[t]=='U':
        ds[0][i]=ds[0][i+1]+1
        ds[1][i]=ds[1][i+1]+1
        ds[2][i]=ds[2][i+1]+1
        ds[3][i]=1
#print(ds)
#dijk
X=[-1,0,1,0]
Y=[0,1,0,-1]
h=[]
val=[[inf]*M for i in range(N)]
val[sy][sx]=0
heappush(h,(0,sy,sx))
while h:
    q,y,x=heappop(h)
    if val[y][x]<q:
        continue
    for k in range(4):
        nx=x+X[k]
        ny=y+Y[k]
        if 0<=nx<M and 0<=ny<N and not S[ny][nx]=='#':
            if val[ny][nx]>val[y][x]+ds[k][q%K]:
                val[ny][nx]=val[y][x]+ds[k][q%K]
                heappush(h,(val[ny][nx],ny,nx))
#print(val)
if val[gy][gx]>=inf:
    print(-1)
else:
    print(val[gy][gx])

Submission Info

Submission Time
Task E - 迷路
User okumura
Language Python3 (3.4.3)
Score 0
Code Size 1470 Byte
Status
Exec Time 2109 ms
Memory 55316 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0
All 0 / 500 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 18 ms 3316 KB
02.txt 18 ms 3316 KB
03.txt 18 ms 3316 KB
04.txt 18 ms 3316 KB
05.txt 18 ms 3316 KB
06.txt 2105 ms 28756 KB
07.txt 2104 ms 28628 KB
08.txt 2105 ms 29140 KB
09.txt 2105 ms 28940 KB
10.txt 2105 ms 28924 KB
11.txt 2105 ms 29332 KB
12.txt 2105 ms 29180 KB
13.txt 2105 ms 28824 KB
14.txt 2105 ms 28788 KB
15.txt 2105 ms 28856 KB
16.txt 2105 ms 29116 KB
17.txt 2105 ms 28184 KB
18.txt 2105 ms 29052 KB
19.txt 2109 ms 29252 KB
20.txt 2104 ms 29496 KB
21.txt 2106 ms 50052 KB
22.txt 2107 ms 49864 KB
23.txt 2106 ms 49968 KB
24.txt 2106 ms 50216 KB
25.txt 2106 ms 49796 KB
26.txt 2107 ms 50220 KB
27.txt 2107 ms 50444 KB
28.txt 2107 ms 49936 KB
29.txt 2107 ms 49740 KB
30.txt 2106 ms 49724 KB
31.txt 416 ms 39924 KB
32.txt 472 ms 39924 KB
33.txt 440 ms 39924 KB
34.txt 424 ms 39924 KB
35.txt 457 ms 39924 KB
36.txt 455 ms 39924 KB
37.txt 441 ms 39924 KB
38.txt 457 ms 39924 KB
39.txt 415 ms 39924 KB
40.txt 2107 ms 55316 KB
41.txt 18 ms 3316 KB
s1.txt 18 ms 3316 KB
s2.txt 18 ms 3316 KB
s3.txt 18 ms 3316 KB