Submission #8814357


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
    dvK = dv % K
    w = v + 1
    if A[w] != '#':
        dw = dv + wait_R[dvK] + 1
        if dist[w] > dw:
            dist[w] = dw
            heappush(q,(dw,w))
    w = v - 1
    if A[w] != '#':
        dw = dv + wait_L[dvK] + 1
        if dist[w] > dw:
            dist[w] = dw
            heappush(q,(dw,w))
    w = v + W
    if A[w] != '#':
        dw = dv + wait_D[dvK] + 1
        if dist[w] > dw:
            dist[w] = dw
            heappush(q,(dw,w))
    w = v - W
    if A[w] != '#':
        dw = dv + wait_U[dvK] + 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 1821 Byte
Status TLE
Exec Time 2117 ms
Memory 216824 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 163 ms 38256 KB
02.txt AC 165 ms 38256 KB
03.txt AC 164 ms 38256 KB
04.txt AC 163 ms 38256 KB
05.txt AC 164 ms 38256 KB
06.txt TLE 2116 ms 200312 KB
07.txt TLE 2115 ms 210680 KB
08.txt TLE 2117 ms 211320 KB
09.txt TLE 2112 ms 147320 KB
10.txt TLE 2115 ms 195704 KB
11.txt TLE 2116 ms 208888 KB
12.txt TLE 2116 ms 199672 KB
13.txt TLE 2117 ms 214008 KB
14.txt TLE 2116 ms 199544 KB
15.txt TLE 2117 ms 211192 KB
16.txt TLE 2116 ms 216824 KB
17.txt TLE 2117 ms 212088 KB
18.txt TLE 2115 ms 192120 KB
19.txt TLE 2116 ms 202360 KB
20.txt TLE 2116 ms 208248 KB
21.txt TLE 2114 ms 169336 KB
22.txt TLE 2116 ms 197368 KB
23.txt TLE 2115 ms 186232 KB
24.txt TLE 2115 ms 191096 KB
25.txt TLE 2113 ms 155768 KB
26.txt TLE 2117 ms 211704 KB
27.txt TLE 2116 ms 199928 KB
28.txt TLE 2115 ms 189304 KB
29.txt TLE 2114 ms 191992 KB
30.txt TLE 2113 ms 157048 KB
31.txt AC 252 ms 81144 KB
32.txt AC 247 ms 81144 KB
33.txt AC 248 ms 81144 KB
34.txt AC 249 ms 81144 KB
35.txt AC 242 ms 80124 KB
36.txt AC 247 ms 81144 KB
37.txt AC 248 ms 81144 KB
38.txt AC 250 ms 81144 KB
39.txt AC 250 ms 81144 KB
40.txt AC 308 ms 81272 KB
41.txt AC 162 ms 38256 KB
s1.txt AC 165 ms 38256 KB
s2.txt AC 164 ms 38256 KB
s3.txt AC 165 ms 38256 KB