Submission #8814346


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 Python (3.4.3)
Score 0
Code Size 1815 Byte
Status TLE
Exec Time 2107 ms
Memory 60232 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 18 ms 3192 KB
02.txt AC 18 ms 3192 KB
03.txt AC 18 ms 3192 KB
04.txt AC 18 ms 3192 KB
05.txt AC 18 ms 3192 KB
06.txt TLE 2106 ms 50016 KB
07.txt TLE 2105 ms 50468 KB
08.txt TLE 2106 ms 50376 KB
09.txt TLE 2106 ms 49060 KB
10.txt TLE 2102 ms 50388 KB
11.txt TLE 2106 ms 50508 KB
12.txt TLE 2105 ms 49848 KB
13.txt TLE 2106 ms 50528 KB
14.txt TLE 2106 ms 50320 KB
15.txt TLE 2106 ms 50260 KB
16.txt TLE 2061 ms 50668 KB
17.txt TLE 2102 ms 50660 KB
18.txt TLE 2106 ms 49900 KB
19.txt TLE 2106 ms 50628 KB
20.txt TLE 2105 ms 50688 KB
21.txt TLE 2107 ms 60144 KB
22.txt TLE 2107 ms 60072 KB
23.txt TLE 2107 ms 60104 KB
24.txt TLE 2099 ms 60152 KB
25.txt TLE 2106 ms 60232 KB
26.txt TLE 2102 ms 60056 KB
27.txt TLE 2107 ms 59612 KB
28.txt TLE 2084 ms 60136 KB
29.txt TLE 2077 ms 60144 KB
30.txt TLE 2106 ms 60080 KB
31.txt AC 215 ms 38296 KB
32.txt AC 215 ms 38292 KB
33.txt AC 249 ms 38296 KB
34.txt AC 226 ms 38300 KB
35.txt AC 215 ms 38300 KB
36.txt AC 225 ms 38296 KB
37.txt AC 215 ms 38292 KB
38.txt AC 213 ms 38300 KB
39.txt AC 214 ms 38300 KB
40.txt AC 1214 ms 58012 KB
41.txt AC 18 ms 3192 KB
s1.txt AC 18 ms 3192 KB
s2.txt AC 18 ms 3192 KB
s3.txt AC 18 ms 3192 KB