Submission #8814374


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 += ['#' + row + '#' for row in read().decode('utf-8').split()]
A += ['#' * (W+2)]

A = list(''.join(A))
start = A.index('S')
goal = A.index('G')
A = [x != '#' for x in A]

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])]

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 1841 Byte
Status TLE
Exec Time 2113 ms
Memory 166592 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 166 ms 38384 KB
02.txt AC 162 ms 38256 KB
03.txt AC 162 ms 38256 KB
04.txt AC 163 ms 38256 KB
05.txt AC 164 ms 38256 KB
06.txt TLE 2113 ms 163836 KB
07.txt TLE 2113 ms 162200 KB
08.txt TLE 2113 ms 166592 KB
09.txt TLE 2112 ms 162736 KB
10.txt TLE 2112 ms 158064 KB
11.txt TLE 2111 ms 148748 KB
12.txt TLE 2111 ms 150668 KB
13.txt TLE 2110 ms 144908 KB
14.txt TLE 2113 ms 158376 KB
15.txt TLE 2111 ms 144652 KB
16.txt TLE 2113 ms 165328 KB
17.txt TLE 2111 ms 149900 KB
18.txt TLE 2111 ms 153432 KB
19.txt TLE 2111 ms 155148 KB
20.txt TLE 2113 ms 158760 KB
21.txt TLE 2112 ms 145384 KB
22.txt TLE 2111 ms 148916 KB
23.txt TLE 2111 ms 146996 KB
24.txt TLE 2111 ms 146996 KB
25.txt TLE 2110 ms 146996 KB
26.txt TLE 2112 ms 147016 KB
27.txt TLE 2110 ms 146444 KB
28.txt TLE 2111 ms 144308 KB
29.txt TLE 2112 ms 151984 KB
30.txt TLE 2111 ms 146996 KB
31.txt AC 380 ms 141236 KB
32.txt AC 389 ms 141236 KB
33.txt AC 386 ms 144180 KB
34.txt AC 380 ms 141236 KB
35.txt AC 379 ms 141236 KB
36.txt AC 381 ms 141236 KB
37.txt AC 383 ms 141236 KB
38.txt AC 382 ms 143156 KB
39.txt AC 374 ms 141236 KB
40.txt AC 443 ms 146868 KB
41.txt AC 162 ms 38256 KB
s1.txt AC 162 ms 38256 KB
s2.txt AC 166 ms 38256 KB
s3.txt AC 164 ms 38256 KB