Buggy python submission (verdict: Runtime Error):
# fast input
from heapq import heappop, heappush
import sys
input = sys.stdin.buffer.readline
INF = 10 ** 10
# INF = float("inf")

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

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


@profile
def main(H, W, K, x1, y1, x2, y2, mapdata):
    # 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 * W + y2

    distances = {}
    # defaultdict(lambda: (INF, 0))
    # distances[(start, 0)] = (0, 0)
    key = (x1 * W + y1) * 5 + 0
    distances[key] = (0, 0)

    shortest_path = {}
    shortest_path[key] = 0

    queue = [((0, 0), key)]
    DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while queue:
        (d, frac), pos_dir = heappop(queue)
        pos, direction = divmod(pos_dir, 5)
        x, y = divmod(pos, W)
        # dp("(frm, direction)", (frm, direction))
        # dp("distances[(frm, direction)]", distances[(frm, direction)])
        dist = distances.get(pos_dir, INF)
        if dist < (d, frac):
            # already know shorter path
            continue
        if pos == goal:
            break

        # same direction
        # dp("direction", direction)
        dx, dy = DIRS[direction]
        nx = x + dx
        ny = y + dy
        # dp("nx, ny", nx, ny)
        if mapdata[nx * W + ny]:
            if frac == 0:
                newd = d + 1
                newfrac = -K + 1
            else:
                newd = d
                newfrac = frac + 1
            newdist = (newd, newfrac)
            to = (nx * W + ny) * 5 + direction

            if distances.get(to, (INF, 0)) > newdist:
                # found shorter path
                distances[to] = newdist
                heappush(queue, (newdist, to))
                shortest_path[to] = pos_dir

        if direction < 2:
            # facing X axis
            dir = 2
            nx = x
            ny = y + 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances.get(to, (INF, 0)) > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 3
            nx = x
            ny = y - 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances.get(to, (INF, 0)) > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir
        else:
            # facing Y axis
            dir = 0
            nx = x + 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances.get(to, (INF, 0)) > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 1
            nx = x - 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances.get(to, (INF, 0)) > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

        # dp("distances", distances)

    dist = min([
        distances.get(goal * 5,  (INF, 0)),
        distances.get(goal * 5 + 1,  (INF, 0)),
        distances.get(goal * 5 + 2,  (INF, 0)),
        distances.get(goal * 5 + 3, (INF, 0)),
    ])
    if dist[0] == INF:
        # unreachable
        print(-1)
    else:
        print(dist[0])


# print(sys.argv)
if sys.argv[-1] == 'ONLINE_JUDGE':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', '(i8,i8,i8,i8,i8,i8,i8,b1[:])')(main)
    # b1[:],i8,i8,i8,i8,i8
    cc.compile()
    exit()
else:
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())

    from my_module import main
    import numpy as np
    C = np.zeros((H + 2, W + 2), np.bool_)
    data = np.frombuffer(
        sys.stdin.buffer.read(),
        'S1')
    # print(data)
    data = data.reshape(H, -1)
    # print(data)
    data = data[:, : W] == b'.'
    # print(data)
    C[1: -1, 1: -1] = data
    C = C.ravel()
    H += 2
    W += 2

    main(H, W, K, x1, y1, x2, y2, C)


Fixed submission:
# fast input
from heapq import heappop, heappush
import sys
input = sys.stdin.buffer.readline
INF = 10 ** 10
# INF = float("inf")

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

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


@profile
def main(H, W, K, x1, y1, x2, y2, mapdata):
    # 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 * W + y1
    goal = x2 * W + y2

    #distances = {}
    distances = [(INF, 0)] * (H * W * 5)
    # defaultdict(lambda: (INF, 0))
    # distances[(start, 0)] = (0, 0)
    key = (x1 * W + y1) * 5 + 4
    distances[key] = (0, 0)

    shortest_path = [0] * (H * W * 5)
    shortest_path[key] = 0

    queue = [((0, 0), key)]
    DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while queue:
        (d, frac), pos_dir = heappop(queue)
        pos, direction = divmod(pos_dir, 5)
        x, y = divmod(pos, W)
        # dp("(frm, direction)", (frm, direction))
        # dp("distances[(frm, direction)]", distances[(frm, direction)])
        dist = distances[pos_dir]
        if dist < (d, frac):
            # already know shorter path
            continue
        if pos == goal:
            break

        # same direction
        # dp("direction", direction)
        if direction != 4:
            dx, dy = DIRS[direction]
            nx = x + dx
            ny = y + dy
            # dp("nx, ny", nx, ny)
            if mapdata[nx * W + ny]:
                if frac == 0:
                    newd = d + 1
                    newfrac = -K + 1
                else:
                    newd = d
                    newfrac = frac + 1
                newdist = (newd, newfrac)
                to = (nx * W + ny) * 5 + direction

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

        if direction < 2 or direction == 4:  # 0, 1, 4
            # facing X axis
            dir = 2
            nx = x
            ny = y + 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 3
            nx = x
            ny = y - 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir
        if direction > 1:  # 2, 3, 4
            # facing Y axis
            dir = 0
            nx = x + 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 1
            nx = x - 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

        # dp("distances", distances)

    result = min(distances[goal * 5:goal * 5+4])
    if result[0] == INF:
        # unreachable
        return -1
    else:
        # cur = pos_dir
        # while cur != start * 5 and cur != 0:
        #     pos, direction = divmod(cur, 5)
        #     x, y = divmod(pos, W)
        #     print(cur, x, y, direction, distances[cur])
        #     cur = shortest_path[cur]
        return result[0]


# print(sys.argv)
if sys.argv[-1] == 'ONLINE_JUDGE':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8,i8,i8,i8,i8,i8,i8,b1[:])')(main)
    # b1[:],i8,i8,i8,i8,i8
    cc.compile()
    exit()
else:
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())

    from my_module import main
    import numpy as np
    C = np.zeros((H + 2, W + 2), np.bool_)
    data = np.frombuffer(
        sys.stdin.buffer.read(),
        'S1')
    # print(data)
    data = data.reshape(H, -1)
    # print(data)
    data = data[:, : W] == b'.'
    # print(data)
    C[1: -1, 1: -1] = data
    C = C.ravel()
    H += 2
    W += 2

    print(main(H, W, K, x1, y1, x2, y2, C))

Buggy python submission (verdict: Time Limit Exceeded):
# fast input
from heapq import heappop, heappush
import sys
input = sys.stdin.buffer.readline
INF = 10 ** 10
# INF = float("inf")

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

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


@profile
def main(H, W, K, x1, y1, x2, y2, mapdata):
    # 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 * W + y2

    distances = {}
    # defaultdict(lambda: (INF, 0))
    # distances[(start, 0)] = (0, 0)
    key = (x1 * W + y1) * 5 + 0
    distances[key] = (0, 0)

    shortest_path = {}
    shortest_path[key] = 0

    queue = [((0, 0), key)]
    DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while queue:
        (d, frac), pos_dir = heappop(queue)
        pos, direction = divmod(pos_dir, 5)
        x, y = divmod(pos, W)
        # dp("(frm, direction)", (frm, direction))
        # dp("distances[(frm, direction)]", distances[(frm, direction)])
        dist = distances.get(pos_dir, INF)
        if dist < (d, frac):
            # already know shorter path
            continue
        if pos == goal:
            break

        # same direction
        # dp("direction", direction)
        dx, dy = DIRS[direction]
        nx = x + dx
        ny = y + dy
        # dp("nx, ny", nx, ny)
        if mapdata[nx * W + ny]:
            if frac == 0:
                newd = d + 1
                newfrac = -K + 1
            else:
                newd = d
                newfrac = frac + 1
            newdist = (newd, newfrac)
            to = (nx * W + ny) * 5 + direction

            if distances.get(to, (INF, 0)) > newdist:
                # found shorter path
                distances[to] = newdist
                heappush(queue, (newdist, to))
                shortest_path[to] = pos_dir

        if direction < 2:
            # facing X axis
            dir = 2
            nx = x
            ny = y + 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances.get(to, (INF, 0)) > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 3
            nx = x
            ny = y - 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances.get(to, (INF, 0)) > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir
        else:
            # facing Y axis
            dir = 0
            nx = x + 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances.get(to, (INF, 0)) > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 1
            nx = x - 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances.get(to, (INF, 0)) > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

        # dp("distances", distances)

    dist = min([
        distances.get(goal * 5,  (INF, 0)),
        distances.get(goal * 5 + 1,  (INF, 0)),
        distances.get(goal * 5 + 2,  (INF, 0)),
        distances.get(goal * 5 + 3, (INF, 0)),
    ])
    if dist[0] == INF:
        # unreachable
        print(-1)
    else:
        print(dist[0])


# print(sys.argv)
if sys.argv[-1] == 'ONLINE_JUDGE':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', '(i8,i8,i8,i8,i8,i8,i8,b1[:])')(main)
    # b1[:],i8,i8,i8,i8,i8
    cc.compile()
    exit()
else:
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())

    # from my_module import main
    import numpy as np
    C = np.zeros((H + 2, W + 2), np.bool_)
    data = np.frombuffer(
        sys.stdin.buffer.read(),
        'S1')
    # print(data)
    data = data.reshape(H, -1)
    # print(data)
    data = data[:, : W] == b'.'
    # print(data)
    C[1: -1, 1: -1] = data
    C = C.ravel()
    H += 2
    W += 2

    main(H, W, K, x1, y1, x2, y2, C)


Fixed submission:
# fast input
from heapq import heappop, heappush
import sys
input = sys.stdin.buffer.readline
INF = 10 ** 10
# INF = float("inf")

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

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


@profile
def main(H, W, K, x1, y1, x2, y2, mapdata):
    # 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 * W + y1
    goal = x2 * W + y2

    #distances = {}
    distances = [(INF, 0)] * (H * W * 5)
    # defaultdict(lambda: (INF, 0))
    # distances[(start, 0)] = (0, 0)
    key = (x1 * W + y1) * 5 + 4
    distances[key] = (0, 0)

    shortest_path = [0] * (H * W * 5)
    shortest_path[key] = 0

    queue = [((0, 0), key)]
    DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while queue:
        (d, frac), pos_dir = heappop(queue)
        pos, direction = divmod(pos_dir, 5)
        x, y = divmod(pos, W)
        # dp("(frm, direction)", (frm, direction))
        # dp("distances[(frm, direction)]", distances[(frm, direction)])
        dist = distances[pos_dir]
        if dist < (d, frac):
            # already know shorter path
            continue
        if pos == goal:
            break

        # same direction
        # dp("direction", direction)
        if direction != 4:
            dx, dy = DIRS[direction]
            nx = x + dx
            ny = y + dy
            # dp("nx, ny", nx, ny)
            if mapdata[nx * W + ny]:
                if frac == 0:
                    newd = d + 1
                    newfrac = -K + 1
                else:
                    newd = d
                    newfrac = frac + 1
                newdist = (newd, newfrac)
                to = (nx * W + ny) * 5 + direction

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

        if direction < 2 or direction == 4:  # 0, 1, 4
            # facing X axis
            dir = 2
            nx = x
            ny = y + 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 3
            nx = x
            ny = y - 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir
        if direction > 1:  # 2, 3, 4
            # facing Y axis
            dir = 0
            nx = x + 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 1
            nx = x - 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

        # dp("distances", distances)

    result = min(distances[goal * 5:goal * 5+4])
    if result[0] == INF:
        # unreachable
        return -1
    else:
        # cur = pos_dir
        # while cur != start * 5 and cur != 0:
        #     pos, direction = divmod(cur, 5)
        #     x, y = divmod(pos, W)
        #     print(cur, x, y, direction, distances[cur])
        #     cur = shortest_path[cur]
        return result[0]


# print(sys.argv)
if sys.argv[-1] == 'ONLINE_JUDGE':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8,i8,i8,i8,i8,i8,i8,b1[:])')(main)
    # b1[:],i8,i8,i8,i8,i8
    cc.compile()
    exit()
else:
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())

    from my_module import main
    import numpy as np
    C = np.zeros((H + 2, W + 2), np.bool_)
    data = np.frombuffer(
        sys.stdin.buffer.read(),
        'S1')
    # print(data)
    data = data.reshape(H, -1)
    # print(data)
    data = data[:, : W] == b'.'
    # print(data)
    C[1: -1, 1: -1] = data
    C = C.ravel()
    H += 2
    W += 2

    print(main(H, W, K, x1, y1, x2, y2, C))

Buggy python submission (verdict: Time Limit Exceeded):
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 = True
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
        # dp("nx, ny", nx, ny)
        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

        if direction < 2:
            # facing X axis
            dir = 2
            nx = x
            ny = y + 1
            if W < ny:
                # dp("out of bounds")
                pass
            elif mapdata[nx - 1][ny - 1] == leaf:
                # dp("hit leaf")
                pass
            else:
                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

            dir = 3
            nx = x
            ny = y - 1
            if ny < 1:
                # dp("out of bounds")
                pass
            elif mapdata[nx - 1][ny - 1] == leaf:
                # dp("hit leaf")
                pass
            else:
                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
        else:
            # facing Y axis
            dir = 0
            nx = x + 1
            ny = y
            if H < nx:
                # dp("out of bounds")
                pass
            elif mapdata[nx - 1][ny - 1] == leaf:
                # dp("hit leaf")
                pass
            else:
                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

            dir = 1
            nx = x - 1
            ny = y
            if nx < 1:
                # dp("out of bounds")
                pass
            elif mapdata[nx - 1][ny - 1] == leaf:
                # dp("hit leaf")
                pass
            else:
                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])


main()


Fixed submission:
# fast input
from heapq import heappop, heappush
import sys
input = sys.stdin.buffer.readline
INF = 10 ** 10
# INF = float("inf")

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

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


@profile
def main(H, W, K, x1, y1, x2, y2, mapdata):
    # 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 * W + y1
    goal = x2 * W + y2

    #distances = {}
    distances = [(INF, 0)] * (H * W * 5)
    # defaultdict(lambda: (INF, 0))
    # distances[(start, 0)] = (0, 0)
    key = (x1 * W + y1) * 5 + 4
    distances[key] = (0, 0)

    shortest_path = [0] * (H * W * 5)
    shortest_path[key] = 0

    queue = [((0, 0), key)]
    DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while queue:
        (d, frac), pos_dir = heappop(queue)
        pos, direction = divmod(pos_dir, 5)
        x, y = divmod(pos, W)
        # dp("(frm, direction)", (frm, direction))
        # dp("distances[(frm, direction)]", distances[(frm, direction)])
        dist = distances[pos_dir]
        if dist < (d, frac):
            # already know shorter path
            continue
        if pos == goal:
            break

        # same direction
        # dp("direction", direction)
        if direction != 4:
            dx, dy = DIRS[direction]
            nx = x + dx
            ny = y + dy
            # dp("nx, ny", nx, ny)
            if mapdata[nx * W + ny]:
                if frac == 0:
                    newd = d + 1
                    newfrac = -K + 1
                else:
                    newd = d
                    newfrac = frac + 1
                newdist = (newd, newfrac)
                to = (nx * W + ny) * 5 + direction

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

        if direction < 2 or direction == 4:  # 0, 1, 4
            # facing X axis
            dir = 2
            nx = x
            ny = y + 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 3
            nx = x
            ny = y - 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir
        if direction > 1:  # 2, 3, 4
            # facing Y axis
            dir = 0
            nx = x + 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 1
            nx = x - 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

        # dp("distances", distances)

    result = min(distances[goal * 5:goal * 5+4])
    if result[0] == INF:
        # unreachable
        return -1
    else:
        # cur = pos_dir
        # while cur != start * 5 and cur != 0:
        #     pos, direction = divmod(cur, 5)
        #     x, y = divmod(pos, W)
        #     print(cur, x, y, direction, distances[cur])
        #     cur = shortest_path[cur]
        return result[0]


# print(sys.argv)
if sys.argv[-1] == 'ONLINE_JUDGE':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8,i8,i8,i8,i8,i8,i8,b1[:])')(main)
    # b1[:],i8,i8,i8,i8,i8
    cc.compile()
    exit()
else:
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())

    from my_module import main
    import numpy as np
    C = np.zeros((H + 2, W + 2), np.bool_)
    data = np.frombuffer(
        sys.stdin.buffer.read(),
        'S1')
    # print(data)
    data = data.reshape(H, -1)
    # print(data)
    data = data[:, : W] == b'.'
    # print(data)
    C[1: -1, 1: -1] = data
    C = C.ravel()
    H += 2
    W += 2

    print(main(H, W, K, x1, y1, x2, y2, C))

Buggy python submission (verdict: Time Limit Exceeded):
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()


Fixed submission:
# fast input
from heapq import heappop, heappush
import sys
input = sys.stdin.buffer.readline
INF = 10 ** 10
# INF = float("inf")

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

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


@profile
def main(H, W, K, x1, y1, x2, y2, mapdata):
    # 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 * W + y1
    goal = x2 * W + y2

    #distances = {}
    distances = [(INF, 0)] * (H * W * 5)
    # defaultdict(lambda: (INF, 0))
    # distances[(start, 0)] = (0, 0)
    key = (x1 * W + y1) * 5 + 4
    distances[key] = (0, 0)

    shortest_path = [0] * (H * W * 5)
    shortest_path[key] = 0

    queue = [((0, 0), key)]
    DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while queue:
        (d, frac), pos_dir = heappop(queue)
        pos, direction = divmod(pos_dir, 5)
        x, y = divmod(pos, W)
        # dp("(frm, direction)", (frm, direction))
        # dp("distances[(frm, direction)]", distances[(frm, direction)])
        dist = distances[pos_dir]
        if dist < (d, frac):
            # already know shorter path
            continue
        if pos == goal:
            break

        # same direction
        # dp("direction", direction)
        if direction != 4:
            dx, dy = DIRS[direction]
            nx = x + dx
            ny = y + dy
            # dp("nx, ny", nx, ny)
            if mapdata[nx * W + ny]:
                if frac == 0:
                    newd = d + 1
                    newfrac = -K + 1
                else:
                    newd = d
                    newfrac = frac + 1
                newdist = (newd, newfrac)
                to = (nx * W + ny) * 5 + direction

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

        if direction < 2 or direction == 4:  # 0, 1, 4
            # facing X axis
            dir = 2
            nx = x
            ny = y + 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 3
            nx = x
            ny = y - 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir
        if direction > 1:  # 2, 3, 4
            # facing Y axis
            dir = 0
            nx = x + 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 1
            nx = x - 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

        # dp("distances", distances)

    result = min(distances[goal * 5:goal * 5+4])
    if result[0] == INF:
        # unreachable
        return -1
    else:
        # cur = pos_dir
        # while cur != start * 5 and cur != 0:
        #     pos, direction = divmod(cur, 5)
        #     x, y = divmod(pos, W)
        #     print(cur, x, y, direction, distances[cur])
        #     cur = shortest_path[cur]
        return result[0]


# print(sys.argv)
if sys.argv[-1] == 'ONLINE_JUDGE':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8,i8,i8,i8,i8,i8,i8,b1[:])')(main)
    # b1[:],i8,i8,i8,i8,i8
    cc.compile()
    exit()
else:
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())

    from my_module import main
    import numpy as np
    C = np.zeros((H + 2, W + 2), np.bool_)
    data = np.frombuffer(
        sys.stdin.buffer.read(),
        'S1')
    # print(data)
    data = data.reshape(H, -1)
    # print(data)
    data = data[:, : W] == b'.'
    # print(data)
    C[1: -1, 1: -1] = data
    C = C.ravel()
    H += 2
    W += 2

    print(main(H, W, K, x1, y1, x2, y2, C))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from heapq import *

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


def profile(f): return f


@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)
    distances[start] = 0
    shortest_path = {}
    shortest_path[start] = None

    maxdist = max(H, W)

    leaf = ord("@")

    queue = [(0, start)]
    while queue:
        d, frm = heappop(queue)
        # print("from", frm)
        if distances[frm] < d:
            # already know shorter path
            continue
        if frm == goal:  # goal
            break

        x, y = frm
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x
            ny = y
            for dist in range(1, maxdist):
                nx += dx
                ny += dy
                if nx < 1 or H < nx or ny < 1 or W < ny:
                    # print("out of bounds")
                    break
                # print(nx, ny, data[nx - 1][ny - 1])
                if mapdata[nx - 1][ny - 1] == leaf:
                    # print("hit leaf")
                    break
                cost = (dist - 1) // K + 1
                to = (nx, ny)
                if distances[to] > distances[frm] + cost:
                    # found shorter path
                    distances[to] = distances[frm] + cost
                    heappush(queue, (distances[to], to))
                    shortest_path[to] = frm
        # print(distances)

    if distances[goal] == INF:
        # unreachable
        print(-1)
    else:
        path = []
        cur = goal
        print(distances[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()


Fixed submission:
# fast input
from heapq import heappop, heappush
import sys
input = sys.stdin.buffer.readline
INF = 10 ** 10
# INF = float("inf")

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

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


@profile
def main(H, W, K, x1, y1, x2, y2, mapdata):
    # 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 * W + y1
    goal = x2 * W + y2

    #distances = {}
    distances = [(INF, 0)] * (H * W * 5)
    # defaultdict(lambda: (INF, 0))
    # distances[(start, 0)] = (0, 0)
    key = (x1 * W + y1) * 5 + 4
    distances[key] = (0, 0)

    shortest_path = [0] * (H * W * 5)
    shortest_path[key] = 0

    queue = [((0, 0), key)]
    DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while queue:
        (d, frac), pos_dir = heappop(queue)
        pos, direction = divmod(pos_dir, 5)
        x, y = divmod(pos, W)
        # dp("(frm, direction)", (frm, direction))
        # dp("distances[(frm, direction)]", distances[(frm, direction)])
        dist = distances[pos_dir]
        if dist < (d, frac):
            # already know shorter path
            continue
        if pos == goal:
            break

        # same direction
        # dp("direction", direction)
        if direction != 4:
            dx, dy = DIRS[direction]
            nx = x + dx
            ny = y + dy
            # dp("nx, ny", nx, ny)
            if mapdata[nx * W + ny]:
                if frac == 0:
                    newd = d + 1
                    newfrac = -K + 1
                else:
                    newd = d
                    newfrac = frac + 1
                newdist = (newd, newfrac)
                to = (nx * W + ny) * 5 + direction

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

        if direction < 2 or direction == 4:  # 0, 1, 4
            # facing X axis
            dir = 2
            nx = x
            ny = y + 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 3
            nx = x
            ny = y - 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir
        if direction > 1:  # 2, 3, 4
            # facing Y axis
            dir = 0
            nx = x + 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 1
            nx = x - 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

        # dp("distances", distances)

    result = min(distances[goal * 5:goal * 5+4])
    if result[0] == INF:
        # unreachable
        return -1
    else:
        # cur = pos_dir
        # while cur != start * 5 and cur != 0:
        #     pos, direction = divmod(cur, 5)
        #     x, y = divmod(pos, W)
        #     print(cur, x, y, direction, distances[cur])
        #     cur = shortest_path[cur]
        return result[0]


# print(sys.argv)
if sys.argv[-1] == 'ONLINE_JUDGE':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8,i8,i8,i8,i8,i8,i8,b1[:])')(main)
    # b1[:],i8,i8,i8,i8,i8
    cc.compile()
    exit()
else:
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())

    from my_module import main
    import numpy as np
    C = np.zeros((H + 2, W + 2), np.bool_)
    data = np.frombuffer(
        sys.stdin.buffer.read(),
        'S1')
    # print(data)
    data = data.reshape(H, -1)
    # print(data)
    data = data[:, : W] == b'.'
    # print(data)
    C[1: -1, 1: -1] = data
    C = C.ravel()
    H += 2
    W += 2

    print(main(H, W, K, x1, y1, x2, y2, C))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from heapq import *

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


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)
    distances[start] = 0
    shortest_path = {}
    shortest_path[start] = None

    maxdist = max(H, W)

    leaf = ord("@")

    def neighbor(frm):
        "return (to, cost)"
        x, y = frm
        # print("frm", frm)
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x
            ny = y
            for dist in range(1, maxdist):
                nx += dx
                ny += dy
                if nx < 1 or H < nx or ny < 1 or W < ny:
                    # print("out of bounds")
                    break
                # print(nx, ny, data[nx - 1][ny - 1])
                if mapdata[nx - 1][ny - 1] == leaf:
                    # print("hit leaf")
                    break
                cost = (dist - 1) // K + 1
                yield ((nx, ny), cost)

    queue = [(0, start)]
    while queue:
        d, frm = heappop(queue)
        # print("from", frm)
        if distances[frm] < d:
            # already know shorter path
            continue
        if frm == goal:  # goal
            break
        for to, cost in neighbor(frm):
            if distances[to] > distances[frm] + cost:
                # found shorter path
                distances[to] = distances[frm] + cost
                heappush(queue, (distances[to], to))
                shortest_path[to] = frm
        # print(distances)

    if distances[goal] == INF:
        # unreachable
        print(-1)
    else:
        path = []
        cur = goal
        print(distances[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()


Fixed submission:
# fast input
from heapq import heappop, heappush
import sys
input = sys.stdin.buffer.readline
INF = 10 ** 10
# INF = float("inf")

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

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


@profile
def main(H, W, K, x1, y1, x2, y2, mapdata):
    # 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 * W + y1
    goal = x2 * W + y2

    #distances = {}
    distances = [(INF, 0)] * (H * W * 5)
    # defaultdict(lambda: (INF, 0))
    # distances[(start, 0)] = (0, 0)
    key = (x1 * W + y1) * 5 + 4
    distances[key] = (0, 0)

    shortest_path = [0] * (H * W * 5)
    shortest_path[key] = 0

    queue = [((0, 0), key)]
    DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while queue:
        (d, frac), pos_dir = heappop(queue)
        pos, direction = divmod(pos_dir, 5)
        x, y = divmod(pos, W)
        # dp("(frm, direction)", (frm, direction))
        # dp("distances[(frm, direction)]", distances[(frm, direction)])
        dist = distances[pos_dir]
        if dist < (d, frac):
            # already know shorter path
            continue
        if pos == goal:
            break

        # same direction
        # dp("direction", direction)
        if direction != 4:
            dx, dy = DIRS[direction]
            nx = x + dx
            ny = y + dy
            # dp("nx, ny", nx, ny)
            if mapdata[nx * W + ny]:
                if frac == 0:
                    newd = d + 1
                    newfrac = -K + 1
                else:
                    newd = d
                    newfrac = frac + 1
                newdist = (newd, newfrac)
                to = (nx * W + ny) * 5 + direction

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

        if direction < 2 or direction == 4:  # 0, 1, 4
            # facing X axis
            dir = 2
            nx = x
            ny = y + 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 3
            nx = x
            ny = y - 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir
        if direction > 1:  # 2, 3, 4
            # facing Y axis
            dir = 0
            nx = x + 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 1
            nx = x - 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

        # dp("distances", distances)

    result = min(distances[goal * 5:goal * 5+4])
    if result[0] == INF:
        # unreachable
        return -1
    else:
        # cur = pos_dir
        # while cur != start * 5 and cur != 0:
        #     pos, direction = divmod(cur, 5)
        #     x, y = divmod(pos, W)
        #     print(cur, x, y, direction, distances[cur])
        #     cur = shortest_path[cur]
        return result[0]


# print(sys.argv)
if sys.argv[-1] == 'ONLINE_JUDGE':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8,i8,i8,i8,i8,i8,i8,b1[:])')(main)
    # b1[:],i8,i8,i8,i8,i8
    cc.compile()
    exit()
else:
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())

    from my_module import main
    import numpy as np
    C = np.zeros((H + 2, W + 2), np.bool_)
    data = np.frombuffer(
        sys.stdin.buffer.read(),
        'S1')
    # print(data)
    data = data.reshape(H, -1)
    # print(data)
    data = data[:, : W] == b'.'
    # print(data)
    C[1: -1, 1: -1] = data
    C = C.ravel()
    H += 2
    W += 2

    print(main(H, W, K, x1, y1, x2, y2, C))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from heapq import *

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

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

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

maxdist = max(H, W)

leaf = ord("@")


def neighbor(frm):
    "return (to, cost)"
    x, y = frm
    # print("frm", frm)
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nx = x
        ny = y
        for dist in range(1, maxdist):
            nx += dx
            ny += dy
            if nx < 1 or H < nx or ny < 1 or W < ny:
                # print("out of bounds")
                break
            # print(nx, ny, data[nx - 1][ny - 1])
            if map[nx - 1][ny - 1] == leaf:
                # print("hit leaf")
                break
            cost = (dist - 1) // K + 1
            yield ((nx, ny), cost)


queue = [(0, start)]
while queue:
    d, frm = heappop(queue)
    # print("from", frm)
    if distances[frm] < d:
        # already know shorter path
        continue
    if frm == goal:  # goal
        break
    for to, cost in neighbor(frm):
        if distances[to] > distances[frm] + cost:
            # found shorter path
            distances[to] = distances[frm] + cost
            heappush(queue, (distances[to], to))
            shortest_path[to] = frm
    # print(distances)

if distances[goal] == INF:
    # unreachable
    print(-1)
else:
    path = []
    cur = goal
    print(distances[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)


Fixed submission:
# fast input
from heapq import heappop, heappush
import sys
input = sys.stdin.buffer.readline
INF = 10 ** 10
# INF = float("inf")

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

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


@profile
def main(H, W, K, x1, y1, x2, y2, mapdata):
    # 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 * W + y1
    goal = x2 * W + y2

    #distances = {}
    distances = [(INF, 0)] * (H * W * 5)
    # defaultdict(lambda: (INF, 0))
    # distances[(start, 0)] = (0, 0)
    key = (x1 * W + y1) * 5 + 4
    distances[key] = (0, 0)

    shortest_path = [0] * (H * W * 5)
    shortest_path[key] = 0

    queue = [((0, 0), key)]
    DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while queue:
        (d, frac), pos_dir = heappop(queue)
        pos, direction = divmod(pos_dir, 5)
        x, y = divmod(pos, W)
        # dp("(frm, direction)", (frm, direction))
        # dp("distances[(frm, direction)]", distances[(frm, direction)])
        dist = distances[pos_dir]
        if dist < (d, frac):
            # already know shorter path
            continue
        if pos == goal:
            break

        # same direction
        # dp("direction", direction)
        if direction != 4:
            dx, dy = DIRS[direction]
            nx = x + dx
            ny = y + dy
            # dp("nx, ny", nx, ny)
            if mapdata[nx * W + ny]:
                if frac == 0:
                    newd = d + 1
                    newfrac = -K + 1
                else:
                    newd = d
                    newfrac = frac + 1
                newdist = (newd, newfrac)
                to = (nx * W + ny) * 5 + direction

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

        if direction < 2 or direction == 4:  # 0, 1, 4
            # facing X axis
            dir = 2
            nx = x
            ny = y + 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 3
            nx = x
            ny = y - 1
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir
        if direction > 1:  # 2, 3, 4
            # facing Y axis
            dir = 0
            nx = x + 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

            dir = 1
            nx = x - 1
            ny = y
            if mapdata[nx * W + ny]:
                newdist = (d + 1, -K + 1)

                to = (nx * W + ny) * 5 + dir
                if distances[to] > newdist:
                    # found shorter path
                    distances[to] = newdist
                    heappush(queue, (newdist, to))
                    shortest_path[to] = pos_dir

        # dp("distances", distances)

    result = min(distances[goal * 5:goal * 5+4])
    if result[0] == INF:
        # unreachable
        return -1
    else:
        # cur = pos_dir
        # while cur != start * 5 and cur != 0:
        #     pos, direction = divmod(cur, 5)
        #     x, y = divmod(pos, W)
        #     print(cur, x, y, direction, distances[cur])
        #     cur = shortest_path[cur]
        return result[0]


# print(sys.argv)
if sys.argv[-1] == 'ONLINE_JUDGE':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', 'i8(i8,i8,i8,i8,i8,i8,i8,b1[:])')(main)
    # b1[:],i8,i8,i8,i8,i8
    cc.compile()
    exit()
else:
    H, W, K = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())

    from my_module import main
    import numpy as np
    C = np.zeros((H + 2, W + 2), np.bool_)
    data = np.frombuffer(
        sys.stdin.buffer.read(),
        'S1')
    # print(data)
    data = data.reshape(H, -1)
    # print(data)
    data = data[:, : W] == b'.'
    # print(data)
    C[1: -1, 1: -1] = data
    C = C.ravel()
    H += 2
    W += 2

    print(main(H, W, K, x1, y1, x2, y2, C))