Submission #2997405


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
    if y==gy and x==gx:
        print(q)
        sys.exit()
    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(-1)

Submission Info

Submission Time
Task E - 迷路
User okumura
Language PyPy3 (2.4.0)
Score 500
Code Size 1465 Byte
Status
Exec Time 1826 ms
Memory 95964 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 164 ms 38256 KB
02.txt 161 ms 38256 KB
03.txt 162 ms 38256 KB
04.txt 162 ms 38256 KB
05.txt 161 ms 38256 KB
06.txt 1647 ms 95964 KB
07.txt 1377 ms 89564 KB
08.txt 1491 ms 87004 KB
09.txt 1333 ms 82140 KB
10.txt 1303 ms 84188 KB
11.txt 1266 ms 79580 KB
12.txt 1826 ms 91868 KB
13.txt 1516 ms 83804 KB
14.txt 1726 ms 87004 KB
15.txt 1521 ms 84700 KB
16.txt 397 ms 71516 KB
17.txt 889 ms 76148 KB
18.txt 875 ms 81884 KB
19.txt 583 ms 73948 KB
20.txt 1236 ms 80860 KB
21.txt 1597 ms 78044 KB
22.txt 1681 ms 81244 KB
23.txt 1697 ms 83940 KB
24.txt 1602 ms 79324 KB
25.txt 1634 ms 78172 KB
26.txt 1580 ms 75740 KB
27.txt 1689 ms 80092 KB
28.txt 1597 ms 78556 KB
29.txt 1646 ms 80860 KB
30.txt 1699 ms 81244 KB
31.txt 262 ms 62940 KB
32.txt 267 ms 63452 KB
33.txt 269 ms 63452 KB
34.txt 264 ms 62940 KB
35.txt 265 ms 63452 KB
36.txt 264 ms 62940 KB
37.txt 264 ms 63452 KB
38.txt 264 ms 63452 KB
39.txt 271 ms 63452 KB
40.txt 398 ms 65628 KB
41.txt 161 ms 38256 KB
s1.txt 162 ms 38256 KB
s2.txt 161 ms 38256 KB
s3.txt 161 ms 38256 KB