Submission #8814482

---

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
wait_U = [INF] * (K+K+1)
wait_D = [INF] * (K+K+1)
wait_R = [INF] * (K+K+1)
wait_L = [INF] * (K+K+1)
for n in range(K+K-1,-1,-1):
    s = S[n]
    wait_U[n] = 0 if s == 'U' else wait_U[n+1] + 1
    wait_D[n] = 0 if s == 'D' else wait_D[n+1] + 1
    wait_R[n] = 0 if s == 'R' else wait_R[n+1] + 1
    wait_L[n] = 0 if s == 'L' else wait_L[n+1] + 1

H += 2; W += 2
dist = [INF] * (H * W)
mask = (1 << 21) - 1
q = [start]
dist[start] = 0
while q:
    x = heappop(q)
    dv = x >> 21
    v = x & mask
    if v == goal:
        break
    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 << 21) + w))
    w = v - 1
    if A[w]:
        dw = dv + wait_L[dvK] + 1
        if dist[w] > dw:
            dist[w] = dw
            heappush(q,((dw << 21) + w))
    w = v + W
    if A[w]:
        dw = dv + wait_D[dvK] + 1
        if dist[w] > dw:
            dist[w] = dw
            heappush(q,((dw << 21) + w))
    w = v - W
    if A[w]:
        dw = dv + wait_U[dvK] + 1
        if dist[w] > dw:
            dist[w] = dw
            heappush(q,((dw << 21) + w))

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

Submission Info

Judge Result