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


def main():
    h, w, k = map(int, input().split())
    sx, sy, gx, gy = map(int, input().split())
    pond = [input().replace("\n", "") for _ in range(h)]
    
    dist_N = [[None]*w for _ in range(h)]
    dist_S = [[None]*w for _ in range(h)]
    dist_E = [[None]*w for _ in range(h)]
    dist_W = [[None]*w for _ in range(h)]
    
    not_yet = [(0, k-1, sx-1, sy-1, "N")]
    
    while not_yet:
        a, b, x, y, d = heappop(not_yet)
        if d == "N" and dist_N[x][y] == None:
            dist_N[x][y] = (a, b)
            if x > 0 and pond[x-1][y] == "." and dist_N[x-1][y] == None:
                if b == k-1:
                    not_yet.append((a+1, 0, x-1, y, "N"))
                else:
                    not_yet.append((a, b+1, x-1, y, "N"))
            if x < h-1 and pond[x+1][y] == "." and dist_S[x+1][y] == None:
                not_yet.append((a+1, 0, x+1, y, "S"))
            if y > 0 and pond[x][y-1] == "." and dist_W[x][y-1] == None:
                not_yet.append((a+1, 0, x, y-1, "W"))
            if y < w-1 and pond[x][y+1] == "." and dist_E[x][y+1] == None:
                not_yet.append((a+1, 0, x, y+1, "E"))
        if d == "W" and dist_W[x][y] == None:
            dist_W[x][y] = (a, b)
            if x > 0 and pond[x-1][y] == "." and dist_N[x-1][y] == None:
                not_yet.append((a+1, 0, x-1, y, "N"))
            if x < h-1 and pond[x+1][y] == "." and dist_S[x+1][y] == None:
                not_yet.append((a+1, 0, x+1, y, "S"))
            if y > 0 and pond[x][y-1] == "." and dist_W[x][y-1] == None:
                if b == k-1:
                    not_yet.append((a+1, 0, x, y-1, "W"))
                else:
                    not_yet.append((a, b+1, x, y-1, "W"))
            if y < w-1 and pond[x][y+1] == "." and dist_E[x][y+1] == None:
                not_yet.append((a+1, 0, x, y+1, "E"))
        if d == "S" and dist_S[x][y] == None:
            dist_S[x][y] = (a, b)
            if x > 0 and pond[x-1][y] == "." and dist_N[x-1][y] == None:
                not_yet.append((a+1, 0, x-1, y, "N"))
            if x < h-1 and pond[x+1][y] == "." and dist_S[x+1][y] == None:
                if b == k-1:
                    not_yet.append((a+1, 0, x+1, y, "S"))
                else:
                    not_yet.append((a, b+1, x+1, y, "S"))
            if y > 0 and pond[x][y-1] == "." and dist_W[x][y-1] == None:
                not_yet.append((a+1, 0, x, y-1, "W"))
            if y < w-1 and pond[x][y+1] == "." and dist_E[x][y+1] == None:
                not_yet.append((a+1, 0, x, y+1, "E"))
        if d == "E" and dist_E[x][y] == None:
            dist_E[x][y] = (a, b)
            if x > 0 and pond[x-1][y] == "." and dist_N[x-1][y] == None:
                not_yet.append((a+1, 0, x-1, y, "N"))
            if x < h-1 and pond[x+1][y] == "." and dist_S[x+1][y] == None:
                not_yet.append((a+1, 0, x+1, y, "S"))
            if y > 0 and pond[x][y-1] == "." and dist_W[x][y-1] == None:
                not_yet.append((a+1, 0, x, y-1, "W"))
            if y < w-1 and pond[x][y+1] == "." and dist_E[x][y+1] == None:
                if b == k-1:
                    not_yet.append((a+1, 0, x, y+1, "E"))
                else:
                    not_yet.append((a, b+1, x, y+1, "E"))
        
    gx -= 1
    gy -= 1
    ans = [10**7]
    
    for v in [dist_N[gx][gy], dist_S[gx][gy], dist_E[gx][gy], dist_W[gx][gy]]:
        if v != None:
            ans.append(v[0])
    
    answer = min(ans)
    print(-1 if answer == 10**7 else answer)
    
        
        
        
    
    
    
    
if __name__ == "__main__":
    main()


Fixed submission:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    h, w, k = map(int, input().split())
    sx, sy, gx, gy = map(int, input().split())

    c = [input() for i in range(h)]

    not_yet = deque([(sx-1, sy-1)])
    dist = [[-1]*w for i in range(h)]
    dist[sx-1][sy-1] = 0
    already = [[False]*w for i in range(h)]
    already[sx-1][sy-1] = True

    while not_yet:
        x, y = not_yet.popleft()
        d = dist[x][y]

        for i in range(x+1, x+k+1):
            if i >= h or c[i][y] == "@":
                break
            if already[i][y] and dist[i][y] < d + 1:
                break
            if already[i][y] and dist[i][y] == d + 1:
                continue
            dist[i][y] = d + 1
            already[i][y] = True
            not_yet.append((i, y))

        for i in range(x-1, x-k-1, -1):
            if i < 0 or c[i][y] == "@":
                break
            if already[i][y] and dist[i][y] < d + 1:
                break
            if already[i][y] and dist[i][y] == d + 1:
                continue
            dist[i][y] = d + 1
            already[i][y] = True
            not_yet.append((i, y))
        
        for i in range(y+1, y+k+1):
            if i >= w or c[x][i] == "@":
                break
            if already[x][i] and dist[x][i] < d + 1:
                break
            if already[x][i] and dist[x][i] == d + 1:
                continue
            dist[x][i] = d + 1
            already[x][i] = True
            not_yet.append((x, i))

        for i in range(y-1, y-k-1, -1):
            if i < 0 or c[x][i] == "@":
                break
            if already[x][i] and dist[x][i] < d + 1:
                break
            if already[x][i] and dist[x][i] == d + 1:
                continue
            dist[x][i] = d + 1
            already[x][i] = True
            not_yet.append((x, i))

    ans = dist[gx-1][gy-1]
    print(ans)

    
if __name__ == "__main__":
    main()

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


def main():
    h, w, k = map(int, input().split())
    sx, sy, gx, gy = map(int, input().split())
    pond = [input().replace("\n", "") for _ in range(h)]
    
    dist_N = [[None]*w for _ in range(h)]
    dist_S = [[None]*w for _ in range(h)]
    dist_E = [[None]*w for _ in range(h)]
    dist_W = [[None]*w for _ in range(h)]
    
    not_yet = [(0, k-1, sx-1, sy-1, "N")]
    
    while not_yet:
        a, b, x, y, d = heappop(not_yet)
        if d == "N" and dist_N[x][y] == None:
            dist_N[x][y] = (a, b)
            if x > 0 and pond[x-1][y] == "." and dist_N[x-1][y] == None:
                if b == k-1:
                    not_yet.append((a+1, 0, x-1, y, "N"))
                else:
                    not_yet.append((a, b+1, x-1, y, "N"))
            if x < h-1 and pond[x+1][y] == "." and dist_S[x+1][y] == None:
                not_yet.append((a+1, 0, x+1, y, "S"))
            if y > 0 and pond[x][y-1] == "." and dist_W[x][y-1] == None:
                not_yet.append((a+1, 0, x, y-1, "W"))
            if y < w-1 and pond[x][y+1] == "." and dist_E[x][y+1] == None:
                not_yet.append((a+1, 0, x, y+1, "E"))
        if d == "W" and dist_W[x][y] == None:
            dist_W[x][y] = (a, b)
            if x > 0 and pond[x-1][y] == "." and dist_N[x-1][y] == None:
                not_yet.append((a+1, 0, x-1, y, "N"))
            if x < h-1 and pond[x+1][y] == "." and dist_S[x+1][y] == None:
                not_yet.append((a+1, 0, x+1, y, "S"))
            if y > 0 and pond[x][y-1] == "." and dist_W[x][y-1] == None:
                if b == k-1:
                    not_yet.append((a+1, 0, x, y-1, "W"))
                else:
                    not_yet.append((a, b+1, x, y-1, "W"))
            if y < w-1 and pond[x][y+1] == "." and dist_E[x][y+1] == None:
                not_yet.append((a+1, 0, x, y+1, "E"))
        if d == "S" and dist_S[x][y] == None:
            dist_S[x][y] = (a, b)
            if x > 0 and pond[x-1][y] == "." and dist_N[x-1][y] == None:
                not_yet.append((a+1, 0, x-1, y, "N"))
            if x < h-1 and pond[x+1][y] == "." and dist_S[x+1][y] == None:
                if b == k-1:
                    not_yet.append((a+1, 0, x+1, y, "S"))
                else:
                    not_yet.append((a, b+1, x+1, y, "S"))
            if y > 0 and pond[x][y-1] == "." and dist_W[x][y-1] == None:
                not_yet.append((a+1, 0, x, y-1, "W"))
            if y < w-1 and pond[x][y+1] == "." and dist_E[x][y+1] == None:
                not_yet.append((a+1, 0, x, y+1, "E"))
        if d == "E" and dist_E[x][y] == None:
            dist_E[x][y] = (a, b)
            if x > 0 and pond[x-1][y] == "." and dist_N[x-1][y] == None:
                not_yet.append((a+1, 0, x-1, y, "N"))
            if x < h-1 and pond[x+1][y] == "." and dist_S[x+1][y] == None:
                not_yet.append((a+1, 0, x+1, y, "S"))
            if y > 0 and pond[x][y-1] == "." and dist_W[x][y-1] == None:
                not_yet.append((a+1, 0, x, y-1, "W"))
            if y < w-1 and pond[x][y+1] == "." and dist_E[x][y+1] == None:
                if b == k-1:
                    not_yet.append((a+1, 0, x, y+1, "E"))
                else:
                    not_yet.append((a, b+1, x, y+1, "E"))
        
    gx -= 1
    gy -= 1
    ans = [10**7]
    
    for v in [dist_N[gx][gy], dist_S[gx][gy], dist_E[gx][gy], dist_W[gx][gy]]:
        if v != None:
            ans.append(v[0])
    
    answer = min(ans)
    print(-1 if answer == 10**7 else answer)
    
        
        
        
    
    
    
    
if __name__ == "__main__":
    main()


Fixed submission:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    h, w, k = map(int, input().split())
    sx, sy, gx, gy = map(int, input().split())

    c = [input() for i in range(h)]

    not_yet = deque([(sx-1, sy-1)])
    dist = [[-1]*w for i in range(h)]
    dist[sx-1][sy-1] = 0
    already = [[False]*w for i in range(h)]
    already[sx-1][sy-1] = True

    while not_yet:
        x, y = not_yet.popleft()
        d = dist[x][y]

        for i in range(x+1, x+k+1):
            if i >= h or c[i][y] == "@":
                break
            if already[i][y] and dist[i][y] < d + 1:
                break
            if already[i][y] and dist[i][y] == d + 1:
                continue
            dist[i][y] = d + 1
            already[i][y] = True
            not_yet.append((i, y))

        for i in range(x-1, x-k-1, -1):
            if i < 0 or c[i][y] == "@":
                break
            if already[i][y] and dist[i][y] < d + 1:
                break
            if already[i][y] and dist[i][y] == d + 1:
                continue
            dist[i][y] = d + 1
            already[i][y] = True
            not_yet.append((i, y))
        
        for i in range(y+1, y+k+1):
            if i >= w or c[x][i] == "@":
                break
            if already[x][i] and dist[x][i] < d + 1:
                break
            if already[x][i] and dist[x][i] == d + 1:
                continue
            dist[x][i] = d + 1
            already[x][i] = True
            not_yet.append((x, i))

        for i in range(y-1, y-k-1, -1):
            if i < 0 or c[x][i] == "@":
                break
            if already[x][i] and dist[x][i] < d + 1:
                break
            if already[x][i] and dist[x][i] == d + 1:
                continue
            dist[x][i] = d + 1
            already[x][i] = True
            not_yet.append((x, i))

    ans = dist[gx-1][gy-1]
    print(ans)

    
if __name__ == "__main__":
    main()

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

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

grid = [None]*h
for i in range(h):
  grid[i] = input()

not_yet = deque([])
already = [[False]*w for _ in range(h)]
dist = [[0]*w for _ in range(h)]
judgement_h = [[False]*w for _ in range(h)]
judgement_w = [[False]*w for _ in range(h)]

not_yet.append((x1-1, y1-1))
already[x1-1][y1-1] = True

while not_yet:
  key = not_yet.popleft()
  k1, k2 = key[0], key[1]
  judgement_h[k1][k2] = True
  judgement_w[k1][k2] = True
  
  border = k1
  for i in range(k1-1, max([-1, k1-k-1]), -1):
    if grid[i][k2] == "@":
      break
    border -= 1
  for i in range(max([0, k1-k, border]), k1):
    if judgement_h[i][k2]:
      break
    elif grid[i][k2] == "@":
      continue
    elif not already[i][k2] and grid[i][k2] == ".":
      dist[i][k2] = dist[k1][k2] + 1
      already[i][k2] = True
      not_yet.append((i, k2))
      judgement_h[i][k2] = True
  
  border = k1
  for i in range(k1+1, min([h, k1+k+1])):
    if grid[i][k2] == "@":
      break
    border += 1
  for i in range(min([h-1, k1+k, border]), k1, -1):
    if judgement_h[i][k2]:
      break
    elif grid[i][k2] == "@":
      break
    elif not already[i][k2] and grid[i][k2] == ".":
      dist[i][k2] = dist[k1][k2] + 1
      already[i][k2] = True
      not_yet.append((i, k2))
      judgement_h[i][k2] = True

  border = k2
  for i in range(k2-1, min([-1, k2-k-1]), -1):
    if grid[k1][i] == "@":
      break
    border -= 1
  for i in range(max([0, k2-k]), k2):
    if judgement_w[k1][i] == True:
      break
    elif grid[k1][i] == "@":
      break
    elif not already[k1][i] and grid[k1][i] == ".":
      dist[k1][i] = dist[k1][k2] + 1
      already[k1][i] = True
      not_yet.append((k1, i))
      judgement_w[k1][i] = True
  
  border = k2
  for i in range(k2+1, min([w, k2+k+1])):
    if grid[k1][i] == "@":
      break
    border += 1
  for i in range(min([w-1, k2+k, border]), k2, -1):
    if judgement_w[k1][i] == True:
      break
    elif grid[k1][i] == "@":
      break
    elif not already[k1][i] and grid[k1][i] == ".":
      dist[k1][i] = dist[k1][k2] + 1
      already[k1][i] = True
      not_yet.append((k1, i))
      judgement_w[k1][i] = True
      
if dist[x2-1][y2-1] == 0:
  print(-1)
else:
  print(dist[x2-1][y2-1])

Fixed submission:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    h, w, k = map(int, input().split())
    sx, sy, gx, gy = map(int, input().split())

    c = [input() for i in range(h)]

    not_yet = deque([(sx-1, sy-1)])
    dist = [[-1]*w for i in range(h)]
    dist[sx-1][sy-1] = 0
    already = [[False]*w for i in range(h)]
    already[sx-1][sy-1] = True

    while not_yet:
        x, y = not_yet.popleft()
        d = dist[x][y]

        for i in range(x+1, x+k+1):
            if i >= h or c[i][y] == "@":
                break
            if already[i][y] and dist[i][y] < d + 1:
                break
            if already[i][y] and dist[i][y] == d + 1:
                continue
            dist[i][y] = d + 1
            already[i][y] = True
            not_yet.append((i, y))

        for i in range(x-1, x-k-1, -1):
            if i < 0 or c[i][y] == "@":
                break
            if already[i][y] and dist[i][y] < d + 1:
                break
            if already[i][y] and dist[i][y] == d + 1:
                continue
            dist[i][y] = d + 1
            already[i][y] = True
            not_yet.append((i, y))
        
        for i in range(y+1, y+k+1):
            if i >= w or c[x][i] == "@":
                break
            if already[x][i] and dist[x][i] < d + 1:
                break
            if already[x][i] and dist[x][i] == d + 1:
                continue
            dist[x][i] = d + 1
            already[x][i] = True
            not_yet.append((x, i))

        for i in range(y-1, y-k-1, -1):
            if i < 0 or c[x][i] == "@":
                break
            if already[x][i] and dist[x][i] < d + 1:
                break
            if already[x][i] and dist[x][i] == d + 1:
                continue
            dist[x][i] = d + 1
            already[x][i] = True
            not_yet.append((x, i))

    ans = dist[gx-1][gy-1]
    print(ans)

    
if __name__ == "__main__":
    main()

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

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

grid = [None]*h
for i in range(h):
  grid[i] = input()

not_yet = deque([])
already = [[False]*w for _ in range(h)]
dist = [[0]*w for _ in range(h)]

not_yet.append((x1-1, y1-1))
already[x1-1][y1-1] = True

while not_yet:
  key = not_yet.popleft()
  k1, k2 = key[0], key[1]
  
  for i in range(k1-1, max([-1, k1-k-1]), -1):
    if not already[i][k2] and grid[i][k2] == ".":
      dist[i][k2] = dist[k1][k2] + 1
      already[i][k2] = True
      not_yet.append((i, k2))
    elif grid[i][k2] == "@":
      break
  for i in range(k1+1, min([h, k1+k+1])):
    if not already[i][k2] and grid[i][k2] == ".":
      dist[i][k2] = dist[k1][k2] + 1
      already[i][k2] = True
      not_yet.append((i, k2))
    elif grid[i][k2] == "@":
      break
  for i in range(k2-1, max([-1, k2-k-1]), -1):
    if not already[k1][i] and grid[k1][i] == ".":
      dist[k1][i] = dist[k1][k2] + 1
      already[k1][i] = True
      not_yet.append((k1, i))
    elif grid[k1][i] == "@":
      break
  for i in range(k2+1, min([w, k2+k+1])):
    if not already[k1][i] and grid[k1][i] == ".":
      dist[k1][i] = dist[k1][k2] + 1
      already[k1][i] = True
      not_yet.append((k1, i))
    elif grid[k1][i] == "@":
      break
      
if dist[x2-1][y2-1] == 0:
  print(-1)
else:
  print(dist[x2-1][y2-1])

Fixed submission:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    h, w, k = map(int, input().split())
    sx, sy, gx, gy = map(int, input().split())

    c = [input() for i in range(h)]

    not_yet = deque([(sx-1, sy-1)])
    dist = [[-1]*w for i in range(h)]
    dist[sx-1][sy-1] = 0
    already = [[False]*w for i in range(h)]
    already[sx-1][sy-1] = True

    while not_yet:
        x, y = not_yet.popleft()
        d = dist[x][y]

        for i in range(x+1, x+k+1):
            if i >= h or c[i][y] == "@":
                break
            if already[i][y] and dist[i][y] < d + 1:
                break
            if already[i][y] and dist[i][y] == d + 1:
                continue
            dist[i][y] = d + 1
            already[i][y] = True
            not_yet.append((i, y))

        for i in range(x-1, x-k-1, -1):
            if i < 0 or c[i][y] == "@":
                break
            if already[i][y] and dist[i][y] < d + 1:
                break
            if already[i][y] and dist[i][y] == d + 1:
                continue
            dist[i][y] = d + 1
            already[i][y] = True
            not_yet.append((i, y))
        
        for i in range(y+1, y+k+1):
            if i >= w or c[x][i] == "@":
                break
            if already[x][i] and dist[x][i] < d + 1:
                break
            if already[x][i] and dist[x][i] == d + 1:
                continue
            dist[x][i] = d + 1
            already[x][i] = True
            not_yet.append((x, i))

        for i in range(y-1, y-k-1, -1):
            if i < 0 or c[x][i] == "@":
                break
            if already[x][i] and dist[x][i] < d + 1:
                break
            if already[x][i] and dist[x][i] == d + 1:
                continue
            dist[x][i] = d + 1
            already[x][i] = True
            not_yet.append((x, i))

    ans = dist[gx-1][gy-1]
    print(ans)

    
if __name__ == "__main__":
    main()

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

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

grid = [None]*h
for i in range(h):
  grid[i] = input()

not_yet = deque([])
already = [[False]*w for _ in range(h)]
dist = [[0]*w for _ in range(h)]

not_yet.append((x1-1, y1-1))
already[x1-1][y1-1] = True

while not_yet:
  key = not_yet.popleft()
  k1, k2 = key[0], key[1]
  
  for i in range(k1-1, max([-1, k1-k-1]), -1):
    if not already[i][k2] and grid[i][k2] == ".":
      dist[i][k2] = dist[k1][k2] + 1
      already[i][k2] = True
      not_yet.append((i, k2))
    elif grid[i][k2] == "@":
      break
  for i in range(k1+1, min([h, k1+k+1])):
    if not already[i][k2] and grid[i][k2] == ".":
      dist[i][k2] = dist[k1][k2] + 1
      already[i][k2] = True
      not_yet.append((i, k2))
    elif grid[i][k2] == "@":
      break
  for i in range(k2-1, max([-1, k2-k-1]), -1):
    if not already[k1][i] and grid[k1][i] == ".":
      dist[k1][i] = dist[k1][k2] + 1
      already[k1][i] = True
      not_yet.append((k1, i))
    elif grid[k1][i] == "@":
      break
  for i in range(k2+1, min([w, k2+k+1])):
    if not already[k1][i] and grid[k1][i] == ".":
      dist[k1][i] = dist[k1][k2] + 1
      already[k1][i] = True
      not_yet.append((k1, i))
    elif grid[k1][i] == "@":
      break

if dist[x2-1][y2-1] == 0:
  print(-1)
else:
  print(dist[x2-1][y2-1])

Fixed submission:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    h, w, k = map(int, input().split())
    sx, sy, gx, gy = map(int, input().split())

    c = [input() for i in range(h)]

    not_yet = deque([(sx-1, sy-1)])
    dist = [[-1]*w for i in range(h)]
    dist[sx-1][sy-1] = 0
    already = [[False]*w for i in range(h)]
    already[sx-1][sy-1] = True

    while not_yet:
        x, y = not_yet.popleft()
        d = dist[x][y]

        for i in range(x+1, x+k+1):
            if i >= h or c[i][y] == "@":
                break
            if already[i][y] and dist[i][y] < d + 1:
                break
            if already[i][y] and dist[i][y] == d + 1:
                continue
            dist[i][y] = d + 1
            already[i][y] = True
            not_yet.append((i, y))

        for i in range(x-1, x-k-1, -1):
            if i < 0 or c[i][y] == "@":
                break
            if already[i][y] and dist[i][y] < d + 1:
                break
            if already[i][y] and dist[i][y] == d + 1:
                continue
            dist[i][y] = d + 1
            already[i][y] = True
            not_yet.append((i, y))
        
        for i in range(y+1, y+k+1):
            if i >= w or c[x][i] == "@":
                break
            if already[x][i] and dist[x][i] < d + 1:
                break
            if already[x][i] and dist[x][i] == d + 1:
                continue
            dist[x][i] = d + 1
            already[x][i] = True
            not_yet.append((x, i))

        for i in range(y-1, y-k-1, -1):
            if i < 0 or c[x][i] == "@":
                break
            if already[x][i] and dist[x][i] < d + 1:
                break
            if already[x][i] and dist[x][i] == d + 1:
                continue
            dist[x][i] = d + 1
            already[x][i] = True
            not_yet.append((x, i))

    ans = dist[gx-1][gy-1]
    print(ans)

    
if __name__ == "__main__":
    main()