Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [[i for i in input()] for _ in range(H)]

INF = 1 << 60
dist = [[[INF] * 2 for _ in range(W)] for _ in range(H)]
dist[x1 - 1][y1 - 1] = [0, 0]

# (cost, x, y, mode)
q = [(0, x1 - 1, y1 - 1, 0), (0, x1 - 1, y1 - 1, 1)]
while q :
  ccost, cx, cy, cmode = heappop(q)
  if ccost > dist[cx][cy][cmode] :
    continue
  for i, (dx, dy) in enumerate(((-1, 0), (0, -1), (1, 0), (0, 1))) :
    nmode = i % 2
    nx, ny = cx + dx, cy + dy
    if cmode == nmode :
      ncost = ccost + 1
      if 0 <= nx < H and 0 <= ny < W and c[nx][ny] != '@' and ncost < dist[nx][ny][nmode] :
        heappush(q, (ncost, nx, ny, nmode))
        dist[nx][ny][nmode] = ncost
  ncost = (ccost + K - 1) // K * K
  if ncost < dist[cx][cy][cmode ^ 1] :
    dist[cx][cy][cmode ^ 1] = ncost
    heappush(q, (ncost, cx, cy, cmode ^ 1))
 
if min(dist[x2 - 1][y2 - 1]) == INF :
  print(-1)
else :
  print((min(dist[x2 - 1][y2 - 1]) + K - 1) // K)

Fixed submission:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [[i == '.' for i in input()] for _ in range(H)]

x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
INF = 1 << 60
dist = [INF] * (H * W * 2)

def pos(x, y, m) :
  return (x * W + y) * 2 + m
dist[pos(x1, y1, 0)] = dist[pos(x1, y1, 1)] = 0

q = [(0, pos(x1, y1, 0)), (0, pos(x1, y1, 1))]
while q :
  ccost, cpos = heappop(q)
  if ccost > dist[cpos] : continue
  cx = cpos // 2 // W
  cy = cpos // 2 % W
  cmode = cpos % 2
  dir = [
    [(-1, 0), (1, 0)],
    [(0, -1), (0, 1)]
  ]
  for dx, dy in dir[cmode] :
    nx, ny = cx + dx, cy + dy
    ncost = ccost + 1
    if 0 <= nx < H and 0 <= ny < W and c[nx][ny] and ncost < dist[pos(nx, ny, cmode)] :
      heappush(q, (ncost, pos(nx, ny, cmode)))
      dist[pos(nx, ny, cmode)] = ncost
      
  ncost = (ccost + K - 1) // K * K
  if ncost < dist[pos(cx, cy, cmode ^ 1)] :
    dist[pos(cx, cy, cmode ^ 1)] = ncost
    heappush(q, (ncost, pos(cx, cy, cmode ^ 1)))

ans = min(dist[pos(x2, y2, 0)], dist[pos(x2, y2, 1)])
if ans == INF :
  print(-1)
else :
  print((ans + K - 1) // K)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [[i for i in input()] for _ in range(H)]

dist = [[[float('inf')] * 2 for _ in range(W)] for _ in range(H)]
dist[x1 - 1][y1 - 1] = [0, 0]

# (cost, x, y, mode)
q = [(0, x1 - 1, y1 - 1, 0), (0, x1 - 1, y1 - 1, 1)]
while q :
  ccost, cx, cy, cmode = heappop(q)
  if ccost > dist[cx][cy][cmode] :
    continue
  for i, (dx, dy) in enumerate(((-1, 0), (0, -1), (1, 0), (0, 1))) :
    nmode = i % 2
    nx, ny = cx + dx, cy + dy
    if cmode == nmode :
      ncost = ccost + 1
      if 0 <= nx < H and 0 <= ny < W and c[nx][ny] != '@' and ncost < dist[nx][ny][nmode] :
        heappush(q, (ncost, nx, ny, nmode))
        dist[nx][ny][nmode] = ncost
  ncost = (ccost + K - 1) // K * K
  if ncost < dist[cx][cy][cmode ^ 1] :
    dist[cx][cy][cmode ^ 1] = ncost
    heappush(q, (ncost, cx, cy, cmode ^ 1))
 
if min(dist[x2 - 1][y2 - 1]) == float('inf') :
  print(-1)
else :
  print((min(dist[x2 - 1][y2 - 1]) + K - 1) // K)

Fixed submission:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [[i == '.' for i in input()] for _ in range(H)]

x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
INF = 1 << 60
dist = [INF] * (H * W * 2)

def pos(x, y, m) :
  return (x * W + y) * 2 + m
dist[pos(x1, y1, 0)] = dist[pos(x1, y1, 1)] = 0

q = [(0, pos(x1, y1, 0)), (0, pos(x1, y1, 1))]
while q :
  ccost, cpos = heappop(q)
  if ccost > dist[cpos] : continue
  cx = cpos // 2 // W
  cy = cpos // 2 % W
  cmode = cpos % 2
  dir = [
    [(-1, 0), (1, 0)],
    [(0, -1), (0, 1)]
  ]
  for dx, dy in dir[cmode] :
    nx, ny = cx + dx, cy + dy
    ncost = ccost + 1
    if 0 <= nx < H and 0 <= ny < W and c[nx][ny] and ncost < dist[pos(nx, ny, cmode)] :
      heappush(q, (ncost, pos(nx, ny, cmode)))
      dist[pos(nx, ny, cmode)] = ncost
      
  ncost = (ccost + K - 1) // K * K
  if ncost < dist[pos(cx, cy, cmode ^ 1)] :
    dist[pos(cx, cy, cmode ^ 1)] = ncost
    heappush(q, (ncost, pos(cx, cy, cmode ^ 1)))

ans = min(dist[pos(x2, y2, 0)], dist[pos(x2, y2, 1)])
if ans == INF :
  print(-1)
else :
  print((ans + K - 1) // K)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [[i for i in input()] for _ in range(H)]

dist = [[[float('inf')] * 2 for _ in range(W)] for _ in range(H)]
dist[x1 - 1][y1 - 1] = [0, 0]

# (cost, x, y, mode)
q = [(0, x1 - 1, y1 - 1, 0), (0, x1 - 1, y1 - 1, 1)]
while q :
  ccost, cx, cy, cmode = heappop(q)
  if ccost > dist[cx][cy][cmode] :
    continue
  for i, (dx, dy) in enumerate(((-1, 0), (0, -1), (1, 0), (0, 1))) :
    nmode = i % 2
    nx, ny = cx + dx, cy + dy
    if cmode == nmode :
      ncost = ccost + 1
    else :
      ncost = ccost + K - ccost % K
      
    if 0 <= nx < H and 0 <= ny < W and c[nx][ny] != '@' and ncost < dist[nx][ny][nmode] :
      heappush(q, (ncost, nx, ny, nmode))
      dist[nx][ny][nmode] = ncost
 
if min(dist[x2 - 1][y2 - 1]) == float('inf') :
  print(-1)
else :
  print((min(dist[x2 - 1][y2 - 1]) + K - 1) // K)

Fixed submission:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [[i == '.' for i in input()] for _ in range(H)]

x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
INF = 1 << 60
dist = [INF] * (H * W * 2)

def pos(x, y, m) :
  return (x * W + y) * 2 + m
dist[pos(x1, y1, 0)] = dist[pos(x1, y1, 1)] = 0

q = [(0, pos(x1, y1, 0)), (0, pos(x1, y1, 1))]
while q :
  ccost, cpos = heappop(q)
  if ccost > dist[cpos] : continue
  cx = cpos // 2 // W
  cy = cpos // 2 % W
  cmode = cpos % 2
  dir = [
    [(-1, 0), (1, 0)],
    [(0, -1), (0, 1)]
  ]
  for dx, dy in dir[cmode] :
    nx, ny = cx + dx, cy + dy
    ncost = ccost + 1
    if 0 <= nx < H and 0 <= ny < W and c[nx][ny] and ncost < dist[pos(nx, ny, cmode)] :
      heappush(q, (ncost, pos(nx, ny, cmode)))
      dist[pos(nx, ny, cmode)] = ncost
      
  ncost = (ccost + K - 1) // K * K
  if ncost < dist[pos(cx, cy, cmode ^ 1)] :
    dist[pos(cx, cy, cmode ^ 1)] = ncost
    heappush(q, (ncost, pos(cx, cy, cmode ^ 1)))

ans = min(dist[pos(x2, y2, 0)], dist[pos(x2, y2, 1)])
if ans == INF :
  print(-1)
else :
  print((ans + K - 1) // K)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import  heappush, heappop

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [[i for i in input()] for _ in range(H)]

dist = [[[float('inf')] * 2 for _ in range(W)] for _ in range(H)]
dist[x1 - 1][y1 - 1] = [0, 0]

# [cost, x, y, mode]
q = [(0, x1 - 1, y1 - 1, 0), (0, x1 - 1, y1 - 1, 1)]
while q :
  ccost, cx, cy, cmode = heappop(q)
  if ccost > dist[cx][cy][cmode] :
    continue
  for i, (dx, dy) in enumerate(((-1, 0), (0, -1), (1, 0), (0, 1))) :
    nmode = i % 2
    nx, ny = cx + dx, cy + dy
    if cmode == nmode :
      ncost = ccost + 1
    else :
      ncost = (ccost + K) - ccost % K
      
    if 0 <= nx < H and 0 <= ny < W and c[nx][ny] != '@' and dist[nx][ny][nmode] > ncost :
      heappush(q, (ncost, nx, ny, nmode))
      dist[nx][ny][nmode] = ncost
 
if min(dist[x2 - 1][y2 - 1]) == float('inf') :
  print(-1)
else :
  print((min(dist[x2 - 1][y2 - 1]) + K - 1) // K)

Fixed submission:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [[i == '.' for i in input()] for _ in range(H)]

x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
INF = 1 << 60
dist = [INF] * (H * W * 2)

def pos(x, y, m) :
  return (x * W + y) * 2 + m
dist[pos(x1, y1, 0)] = dist[pos(x1, y1, 1)] = 0

q = [(0, pos(x1, y1, 0)), (0, pos(x1, y1, 1))]
while q :
  ccost, cpos = heappop(q)
  if ccost > dist[cpos] : continue
  cx = cpos // 2 // W
  cy = cpos // 2 % W
  cmode = cpos % 2
  dir = [
    [(-1, 0), (1, 0)],
    [(0, -1), (0, 1)]
  ]
  for dx, dy in dir[cmode] :
    nx, ny = cx + dx, cy + dy
    ncost = ccost + 1
    if 0 <= nx < H and 0 <= ny < W and c[nx][ny] and ncost < dist[pos(nx, ny, cmode)] :
      heappush(q, (ncost, pos(nx, ny, cmode)))
      dist[pos(nx, ny, cmode)] = ncost
      
  ncost = (ccost + K - 1) // K * K
  if ncost < dist[pos(cx, cy, cmode ^ 1)] :
    dist[pos(cx, cy, cmode ^ 1)] = ncost
    heappush(q, (ncost, pos(cx, cy, cmode ^ 1)))

ans = min(dist[pos(x2, y2, 0)], dist[pos(x2, y2, 1)])
if ans == INF :
  print(-1)
else :
  print((ans + K - 1) // K)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import  heappush, heappop

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [[i for i in input()] for _ in range(H)]

dist = [[float('inf')] * W for _ in range(H)]
dist[x1 - 1][y1 - 1] = 0
q = [(0, x1 - 1, y1 - 1)]
while q :
  ccost, cx, cy = heappop(q)
  if ccost > dist[cx][cy] :
    continue
  for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)) :
    for i in range(1, K + 1) :
      nx, ny = dx * i + cx, dy * i + cy
      ncost = ccost + 1
      if not (0 <= nx < H and 0 <= ny < W and c[nx][ny] != '@' and ncost <= dist[nx][ny]) :
        break
      if ncost <= dist[nx][ny] :
        heappush(q, (ncost, nx, ny))
        dist[nx][ny] = ncost

if dist[x2 - 1][y2 - 1] == float('inf') :
  print(-1)
else :
  print(dist[x2 - 1][y2 - 1])

Fixed submission:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [[i == '.' for i in input()] for _ in range(H)]

x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
INF = 1 << 60
dist = [INF] * (H * W * 2)

def pos(x, y, m) :
  return (x * W + y) * 2 + m
dist[pos(x1, y1, 0)] = dist[pos(x1, y1, 1)] = 0

q = [(0, pos(x1, y1, 0)), (0, pos(x1, y1, 1))]
while q :
  ccost, cpos = heappop(q)
  if ccost > dist[cpos] : continue
  cx = cpos // 2 // W
  cy = cpos // 2 % W
  cmode = cpos % 2
  dir = [
    [(-1, 0), (1, 0)],
    [(0, -1), (0, 1)]
  ]
  for dx, dy in dir[cmode] :
    nx, ny = cx + dx, cy + dy
    ncost = ccost + 1
    if 0 <= nx < H and 0 <= ny < W and c[nx][ny] and ncost < dist[pos(nx, ny, cmode)] :
      heappush(q, (ncost, pos(nx, ny, cmode)))
      dist[pos(nx, ny, cmode)] = ncost
      
  ncost = (ccost + K - 1) // K * K
  if ncost < dist[pos(cx, cy, cmode ^ 1)] :
    dist[pos(cx, cy, cmode ^ 1)] = ncost
    heappush(q, (ncost, pos(cx, cy, cmode ^ 1)))

ans = min(dist[pos(x2, y2, 0)], dist[pos(x2, y2, 1)])
if ans == INF :
  print(-1)
else :
  print((ans + K - 1) // K)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import  heappush, heappop

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [[i for i in input()] for _ in range(H)]

dist = [[float('inf')] * W for _ in range(H)]
dist[x1 - 1][y1 - 1] = 0
q = [(0, x1 - 1, y1 - 1)]
while q :
  ccost, cx, cy = heappop(q)
  if ccost > dist[cx][cy] :
    continue
  for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)) :
    for i in range(1, K + 1) :
      nx, ny = dx * i + cx, dy * i + cy
      ncost = ccost + 1
      if not (0 <= nx < H and 0 <= ny < W and c[nx][ny] != '@' and ncost <= dist[nx][ny]) :
        break
      heappush(q, (ncost, nx, ny))
      dist[nx][ny] = ncost

if dist[x2 - 1][y2 - 1] == float('inf') :
  print(-1)
else :
  print(dist[x2 - 1][y2 - 1])

Fixed submission:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [[i == '.' for i in input()] for _ in range(H)]

x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
INF = 1 << 60
dist = [INF] * (H * W * 2)

def pos(x, y, m) :
  return (x * W + y) * 2 + m
dist[pos(x1, y1, 0)] = dist[pos(x1, y1, 1)] = 0

q = [(0, pos(x1, y1, 0)), (0, pos(x1, y1, 1))]
while q :
  ccost, cpos = heappop(q)
  if ccost > dist[cpos] : continue
  cx = cpos // 2 // W
  cy = cpos // 2 % W
  cmode = cpos % 2
  dir = [
    [(-1, 0), (1, 0)],
    [(0, -1), (0, 1)]
  ]
  for dx, dy in dir[cmode] :
    nx, ny = cx + dx, cy + dy
    ncost = ccost + 1
    if 0 <= nx < H and 0 <= ny < W and c[nx][ny] and ncost < dist[pos(nx, ny, cmode)] :
      heappush(q, (ncost, pos(nx, ny, cmode)))
      dist[pos(nx, ny, cmode)] = ncost
      
  ncost = (ccost + K - 1) // K * K
  if ncost < dist[pos(cx, cy, cmode ^ 1)] :
    dist[pos(cx, cy, cmode ^ 1)] = ncost
    heappush(q, (ncost, pos(cx, cy, cmode ^ 1)))

ans = min(dist[pos(x2, y2, 0)], dist[pos(x2, y2, 1)])
if ans == INF :
  print(-1)
else :
  print((ans + K - 1) // K)