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

Test Cases

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
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 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
41.txt 18 ms 3316 KB
s1.txt 18 ms 3316 KB
s2.txt 18 ms 3316 KB
s3.txt 18 ms 3316 KB