Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys

read = sys.stdin.read
readline = sys.stdin.readline

h, w, k = map(int, readline().split())
x1, y1, x2, y2 = map(int, readline().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1

field = [readline() for _ in range(h)]
costs = [[99999999] * w for _ in range(h)]

q = deque([(x1, y1)])
costs[x1][y1] = 0

while q:
    x, y = q.popleft()
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        for i in range(1, k + 1):
            px, py = x + dx * i, y + dy * i
            if not(0 <= px < h and 0 <= py < w) or field[px][py] == '@':
                break
            if costs[px][py] < costs[x][y] + 1:
                break
            costs[px][py] = costs[x][y] + 1
            q.append((px, py))

print(-1 if costs[x2][y2] == 99999999 else costs[x2][y2])


Fixed submission:
from collections import deque
import sys

read = sys.stdin.read
readline = sys.stdin.readline

h, w, k = map(int, readline().split())
x1, y1, x2, y2 = map(int, readline().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1

field = [readline() for _ in range(h)]
costs = [[-1] * w for _ in range(h)]

q = deque([(x1, y1)])
costs[x1][y1] = 0

while q:
    x, y = q.popleft()
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        for i in range(1, k + 1):
            px, py = x + dx * i, y + dy * i
            if not(0 <= px < h and 0 <= py < w) or field[px][py] == '@':
                break
            if 0 <= costs[px][py] < costs[x][y] + 1:
                break
            if costs[px][py] == -1:
                q.append((px, py))
            costs[px][py] = costs[x][y] + 1

print(costs[x2][y2])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys

read = sys.stdin.read
readline = sys.stdin.readline

h, w, k = map(int, readline().split())
x1, y1, x2, y2 = map(int, readline().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1

field = [readline() for _ in range(h)]

visited = [[False] * w for _ in range(h)]
costs = [[-1] * w for _ in range(h)]

q = deque([(x1, y1)])
costs[x1][y1] = 0

while q:
    x, y = q.popleft()
    if visited[x][y]:
        continue
    visited[x][y] = True
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        for i in range(1, k + 1):
            px, py = x + dx * i, y + dy * i
            if not(0 <= px < h and 0 <= py < w) or field[px][py] == '@' or visited[px][py]:
                break
            if costs[px][py] == -1 or costs[px][py] > costs[x][y] + 1:
                costs[px][py] = costs[x][y] + 1
                q.append((px, py))

print(costs[x2][y2])


Fixed submission:
from collections import deque
import sys

read = sys.stdin.read
readline = sys.stdin.readline

h, w, k = map(int, readline().split())
x1, y1, x2, y2 = map(int, readline().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1

field = [readline() for _ in range(h)]
costs = [[-1] * w for _ in range(h)]

q = deque([(x1, y1)])
costs[x1][y1] = 0

while q:
    x, y = q.popleft()
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        for i in range(1, k + 1):
            px, py = x + dx * i, y + dy * i
            if not(0 <= px < h and 0 <= py < w) or field[px][py] == '@':
                break
            if 0 <= costs[px][py] < costs[x][y] + 1:
                break
            if costs[px][py] == -1:
                q.append((px, py))
            costs[px][py] = costs[x][y] + 1

print(costs[x2][y2])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import math
import sys

input = sys.stdin.readline

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1

field = []
for _ in range(h):
    field.append(list(input()))
visited = [[False for _ in range(w)] for _ in range(h)]
costs = [[99999999 for _ in range(w)] for _ in range(h)]


q = deque([(x1, y1)])
costs[x1][y1] = 0

while q:
    x, y = q.popleft()
    if visited[x][y]:
        continue
    visited[x][y] = True
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        for i in range(1, k + 1):
            px, py = x + dx * i, y + dy * i
            if not(0 <= px < h and 0 <= py < w) or field[px][py] == '@' or visited[px][py]:
                break
            if costs[px][py] > costs[x][y] + 1:
                costs[px][py] = costs[x][y] + 1
                q.append((px, py))

print(-1 if costs[x2][y2] == 99999999 else costs[x2][y2])


Fixed submission:
from collections import deque
import sys

read = sys.stdin.read
readline = sys.stdin.readline

h, w, k = map(int, readline().split())
x1, y1, x2, y2 = map(int, readline().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1

field = [readline() for _ in range(h)]
costs = [[-1] * w for _ in range(h)]

q = deque([(x1, y1)])
costs[x1][y1] = 0

while q:
    x, y = q.popleft()
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        for i in range(1, k + 1):
            px, py = x + dx * i, y + dy * i
            if not(0 <= px < h and 0 <= py < w) or field[px][py] == '@':
                break
            if 0 <= costs[px][py] < costs[x][y] + 1:
                break
            if costs[px][py] == -1:
                q.append((px, py))
            costs[px][py] = costs[x][y] + 1

print(costs[x2][y2])

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
import math

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1

field = []
for _ in range(h):
    field.append(list(input()))
visited = [[[False for _ in range(4)] for _ in range(w)] for _ in range(h)]
costs = [[[99999999 for _ in range(4)] for _ in range(w)] for _ in range(h)]


def calc(cost, d):
    ns = []

    # その方向に進む
    if d == 0:
        ns.append((1, 1, 0, d))
    elif d == 1:
        ns.append((1, 0, 1, d))
    elif d == 2:
        ns.append((1, -1, 0, d))
    elif d == 3:
        ns.append((1, 0, -1, d))

    # 方向転換
    if cost % k == 0:
        dcost = 0
    else:
        dcost = k - cost % k
    if d != 0:
        ns.append((dcost, 0, 0, 0))
    if d != 1:
        ns.append((dcost, 0, 0, 1))
    if d != 2:
        ns.append((dcost, 0, 0, 2))
    if d != 3:
        ns.append((dcost, 0, 0, 3))

    return ns


heap = []
heapq.heappush(heap, (0, (x1, y1, 0)))
costs[x1][y1][0] = 0

while heap:
    cost, (x, y, d) = heapq.heappop(heap)
    if visited[x][y][d]:
        continue
    visited[x][y][d] = True
    for dcost, dx, dy, next_d in calc(cost, d):
        if x + dx >= h or x + dx < 0 or y + dy >= w or y + dy < 0 or field[x + dx][y + dy] == '@' or visited[x + dx][y + dy][next_d]:
            continue
        if costs[x + dx][y + dy][next_d] > cost + dcost:
            costs[x + dx][y + dy][next_d] = cost + dcost
            heapq.heappush(heap, (cost + dcost, (x + dx, y + dy, next_d)))

res = min([costs[x2][y2][d] for d in range(4)])
if res == 99999999:
    print(-1)
else:
    print(math.ceil(res / k))


Fixed submission:
from collections import deque
import sys

read = sys.stdin.read
readline = sys.stdin.readline

h, w, k = map(int, readline().split())
x1, y1, x2, y2 = map(int, readline().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1

field = [readline() for _ in range(h)]
costs = [[-1] * w for _ in range(h)]

q = deque([(x1, y1)])
costs[x1][y1] = 0

while q:
    x, y = q.popleft()
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        for i in range(1, k + 1):
            px, py = x + dx * i, y + dy * i
            if not(0 <= px < h and 0 <= py < w) or field[px][py] == '@':
                break
            if 0 <= costs[px][py] < costs[x][y] + 1:
                break
            if costs[px][py] == -1:
                q.append((px, py))
            costs[px][py] = costs[x][y] + 1

print(costs[x2][y2])