Submission #8814348


Source Code Expand

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop

H,W,K = map(int,readline().split())
S = readline().rstrip().decode('utf-8')
A = '#' * (W+2)
A += ''.join('#' + row + '#' for row in read().decode('utf-8').split())
A += '#' * (W+2)

INF = 10 ** 18
S += S
next_U = [INF] * (K+K+1)
next_D = [INF] * (K+K+1)
next_R = [INF] * (K+K+1)
next_L = [INF] * (K+K+1)
for n in range(K+K-1,-1,-1):
    s = S[n]
    next_U[n] = n if s == 'U' else next_U[n+1]
    next_D[n] = n if s == 'D' else next_D[n+1]
    next_R[n] = n if s == 'R' else next_R[n+1]
    next_L[n] = n if s == 'L' else next_L[n+1]

wait_U = [x - i for i,x in enumerate(next_U[:K])]
wait_D = [x - i for i,x in enumerate(next_D[:K])]
wait_R = [x - i for i,x in enumerate(next_R[:K])]
wait_L = [x - i for i,x in enumerate(next_L[:K])]

start = A.find('S')
goal = A.find('G')

H += 2; W += 2
dist = [INF] * (H * W)
q = [(0,start)]
dist[start] = 0
while q:
    dv,v = heappop(q)
    if dist[v] < dv:
        continue
    w = v + 1
    if A[w] != '#':
        dw = dv + wait_R[dv % K] + 1
        if dist[w] > dw:
            dist[w] = dw
            heappush(q,(dw,w))
    w = v - 1
    if A[w] != '#':
        dw = dv + wait_L[dv % K] + 1
        if dist[w] > dw:
            dist[w] = dw
            heappush(q,(dw,w))
    w = v + W
    if A[w] != '#':
        dw = dv + wait_D[dv % K] + 1
        if dist[w] > dw:
            dist[w] = dw
            heappush(q,(dw,w))
    w = v - W
    if A[w] != '#':
        dw = dv + wait_U[dv % K] + 1
        if dist[w] > dw:
            dist[w] = dw
            heappush(q,(dw,w))

answer = dist[goal]
if answer >= INF:
    answer = -1
print(answer)

Submission Info

Submission Time
Task E - 迷路
User maspy
Language PyPy3 (2.4.0)
Score 0
Code Size 1815 Byte
Status TLE
Exec Time 2120 ms
Memory 220152 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status AC
AC × 19
TLE × 25
Set Name Test Cases
Sample
All 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 AC 164 ms 38384 KB
02.txt AC 163 ms 38256 KB
03.txt AC 162 ms 38256 KB
04.txt AC 164 ms 38256 KB
05.txt AC 163 ms 38256 KB
06.txt TLE 2116 ms 206200 KB
07.txt TLE 2116 ms 216440 KB
08.txt TLE 2116 ms 217464 KB
09.txt TLE 2112 ms 148728 KB
10.txt TLE 2115 ms 200696 KB
11.txt TLE 2117 ms 211704 KB
12.txt TLE 2115 ms 202104 KB
13.txt TLE 2117 ms 219640 KB
14.txt TLE 2116 ms 204408 KB
15.txt TLE 2117 ms 216568 KB
16.txt TLE 2117 ms 220152 KB
17.txt TLE 2116 ms 217336 KB
18.txt TLE 2115 ms 194680 KB
19.txt TLE 2116 ms 204536 KB
20.txt TLE 2116 ms 213112 KB
21.txt TLE 2113 ms 171512 KB
22.txt TLE 2116 ms 202744 KB
23.txt TLE 2120 ms 190968 KB
24.txt TLE 2115 ms 196088 KB
25.txt TLE 2113 ms 157688 KB
26.txt TLE 2117 ms 216184 KB
27.txt TLE 2116 ms 203000 KB
28.txt TLE 2115 ms 194552 KB
29.txt TLE 2115 ms 197368 KB
30.txt TLE 2112 ms 158968 KB
31.txt AC 250 ms 81272 KB
32.txt AC 248 ms 81144 KB
33.txt AC 248 ms 81144 KB
34.txt AC 249 ms 81144 KB
35.txt AC 241 ms 80124 KB
36.txt AC 251 ms 81144 KB
37.txt AC 249 ms 81144 KB
38.txt AC 256 ms 81144 KB
39.txt AC 249 ms 81144 KB
40.txt AC 314 ms 81272 KB
41.txt AC 163 ms 38256 KB
s1.txt AC 161 ms 38256 KB
s2.txt AC 162 ms 38256 KB
s3.txt AC 169 ms 38256 KB