Submission #14488691

---

Source Code Expand

from collections import defaultdict
from heapq import *

# fast input
import sys
input = sys.stdin.buffer.readline
INF = 10 ** 10
# INF = float("inf")

try:
    profile
except:
    def profile(f): return f

DEBUG = False
if DEBUG:
    def dp(*x):  # debugprint
        print(*x)
else:
    def dp(*x): pass


@profile
def main():
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    mapdata = sys.stdin.buffer.read().splitlines()
    # print(data)
    start = (x1, y1)
    goal = (x2, y2)

    distances = defaultdict(lambda: (INF, 0))
    distances[(start, 0)] = (0, 0)
    shortest_path = {}
    shortest_path[(start, 0)] = None

    leaf = ord("@")

    queue = [((0, 0), (start, 0))]
    DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while queue:
        (d, frac), (frm, direction) = heappop(queue)
        # dp("(frm, direction)", (frm, direction))
        # dp("distances[(frm, direction)]", distances[(frm, direction)])
        if distances[(frm, direction)] < (d, frac):
            # already know shorter path
            continue
        if frm == goal:
            break

        x, y = frm
        # same direction
        # dp("direction", direction)
        dx, dy = DIRS[direction]
        nx = x + dx
        ny = y + dy
        if nx < 1 or H < nx or ny < 1 or W < ny:
            # dp("out of bounds")
            pass
        elif mapdata[nx - 1][ny - 1] == leaf:
            # dp("hit leaf")
            pass
        else:
            if frac == 0:
                newd = d + 1
                newfrac = -K + 1
            else:
                newd = d
                newfrac = frac + 1
            newdist = (newd, newfrac)
            to = ((nx, ny), direction)

            if distances[to] > newdist:
                # found shorter path
                distances[to] = newdist
                heappush(queue, (newdist, to))
                shortest_path[to] = frm

        for dir in range(4):
            if dir == direction:
                continue
            # dp("dir", dir)
            dx, dy = DIRS[dir]
            # dp("dx, dy", dx, dy)
            nx = x + dx
            ny = y + dy
            # dp("nx, ny", nx, ny)

            if nx < 1 or H < nx or ny < 1 or W < ny:
                # dp("out of bounds")
                continue
            dp(nx, ny, mapdata[nx - 1][ny - 1])
            if mapdata[nx - 1][ny - 1] == leaf:
                # dp("hit leaf")
                continue
            newdist = (d + 1, -K + 1)

            to = ((nx, ny), dir)
            if distances[to] > newdist:
                # found shorter path
                distances[to] = newdist
                heappush(queue, (newdist, to))
                shortest_path[to] = frm
        # dp("distances", distances)

    dist = min(distances[(goal, dir)] for dir in range(4))
    if dist[0] == INF:
        # unreachable
        print(-1)
    else:
        print(dist[0])

        # path = []
        # cur = goal
        # while True:
        #     frm = shortest_path[cur]
        #     path.append(frm)
        #     cur = frm
        #     if frm == start:
        #         break
        # path.reverse()
        # print(len(path))  # edge count
        # for (frm, to) in path:
        #     print(frm, to)


main()

Submission Info

Judge Result