Submission #2997386


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 PyPy3 (2.4.0)
Score 500
Code Size 1470 Byte
Status
Exec Time 1979 ms
Memory 98396 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0
All 500 / 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 168 ms 38512 KB
02.txt 169 ms 38256 KB
03.txt 164 ms 38256 KB
04.txt 164 ms 38256 KB
05.txt 165 ms 38256 KB
06.txt 1979 ms 98396 KB
07.txt 1879 ms 93020 KB
08.txt 1864 ms 90332 KB
09.txt 1784 ms 84956 KB
10.txt 1802 ms 87388 KB
11.txt 1797 ms 83420 KB
12.txt 1934 ms 91996 KB
13.txt 1792 ms 85212 KB
14.txt 1849 ms 87516 KB
15.txt 1817 ms 85980 KB
16.txt 1768 ms 83932 KB
17.txt 1763 ms 82396 KB
18.txt 1971 ms 93532 KB
19.txt 1778 ms 85596 KB
20.txt 1818 ms 84444 KB
21.txt 1631 ms 77404 KB
22.txt 1722 ms 80860 KB
23.txt 1801 ms 83164 KB
24.txt 1635 ms 78684 KB
25.txt 1650 ms 77532 KB
26.txt 1635 ms 75100 KB
27.txt 1669 ms 79324 KB
28.txt 1619 ms 78000 KB
29.txt 1659 ms 80348 KB
30.txt 1737 ms 80476 KB
31.txt 269 ms 62940 KB
32.txt 275 ms 63452 KB
33.txt 274 ms 63452 KB
34.txt 266 ms 62812 KB
35.txt 270 ms 63452 KB
36.txt 268 ms 62940 KB
37.txt 270 ms 63452 KB
38.txt 271 ms 63452 KB
39.txt 270 ms 63452 KB
40.txt 401 ms 65244 KB
41.txt 168 ms 38256 KB
s1.txt 164 ms 38256 KB
s2.txt 164 ms 38256 KB
s3.txt 163 ms 38256 KB