Submission #8814505

---

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

A = list(b''.join(A))
start = A.index(ord('S'))
goal = A.index(ord('G'))
A = [x != ord('#') 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)
u,d,r,l = [ord(x) for x in 'UDRL']
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