Buggy python submission (verdict: Runtime Error):
from collections import deque
import sys

N_MAX = 200000 + 5

H, W, K = map(int, input().split())
sth, stw, glh, glw = map(int, input().split())

INF = 10**6 * K

dp = [[INF for _ in range(W + 2)] for _ in range(H + 2)]

dp[0] = [-1] * (W + 2)
dp[H + 1] = [-1] * (W + 2)
for h in range(1, H + 1):
    s = sys.stdin.readline()
    dp[h][0] = -1
    dp[h][W + 1] = -1
    for w in range(1, W + 1):
        if s[w - 1] == "@":
            dp[h][w] = -1

dp[sth][stw] = 0


# Seen = [[INF]*W for _ in range(H)]
XY = {(1, 0), (-1, 0), (0, 1), (0, -1)}


def bfs(sth, stw, glh, glw):
    next_q = deque()
    next_q.append((sth, stw))

    while len(next_q) != 0:
        # キュー取り出し(先頭)
        h, w = next_q.popleft()
        for dh, dw in XY:
            for sk in range(1, K + 1):
                hs, ws = h + dh * sk, w + dw * sk
                if dp[hs][ws] == -1:
                    break
                if dp[hs][ws] == INF:
                    next_q.append((hs, ws))
                    dp[hs][ws] = dp[h][w] + 1
                elif dp[hs][ws] <= dp[h][w]:
                    # もし、dp[hs][ws] が 今の値以下なら
                    # その先はdp[hs][ws]をもとに 書き込まれている or 今後書き込まれる ので止める
                    break
                # if hs == glh and ws == glw:
                #    return dp[h][w] + 1
    # return -1


def main():
    bfs(sth, stw, glh, glw)

    if dp[glh, glw] == INF:
        print(-1)
    else:
        print(dp[glh, glw])


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin python3
# -*- coding: utf-8 -*-
 
H, W, K = map(int,input().split())
sth, stw, glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1
 
INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
 
from collections import deque
 
def bfs(sth, stw, glh, glw):
    next_q = deque([])
    next_q.append((sth,stw,0))
    Seen[sth][stw] = 0
 
    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, c = next_q.popleft()
        for dh, dw in direc:
            for sk in range(1,K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Seen[hs][ws]==INF:
                    next_q.append((hs,ws,c+1))
                    Seen[hs][ws] = c + 1
                elif Seen[hs][ws]<=c:
                    break
                if hs==glh and ws==glw:
                    return c + 1
    return -1

def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)

if __name__ == '__main__':
    main()

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

N_MAX = 200000 + 5

H, W, K = map(int, input().split())
sth, stw, glh, glw = map(int, input().split())

INF = 10**6 * K

dp = [[INF for _ in range(W+2)] for _ in range(H+2)]

dp[0] = [-1]*(W+2)
dp[H+1] = [-1]*(W+2)
for h in range(1, H+1):
    s = sys.stdin.readline()
    dp[h][0] = -1
    dp[h][W+1] = -1
    for w in range(1, W+1):
        if s[w-1] == "@":
            dp[h][w] = -1

dp[sth][stw] = 0


# Seen = [[INF]*W for _ in range(H)]
XY = {(1, 0), (-1, 0), (0, 1), (0, -1)}


def bfs(sth, stw, glh, glw):
    next_q = deque()
    next_q.append((sth, stw))

    while len(next_q) != 0:
        # キュー取り出し(先頭)
        h, w = next_q.popleft()
        for dh, dw in XY:
            for sk in range(1, K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if dp[hs][ws] == -1:
                    break
                if dp[hs][ws] == INF:
                    next_q.append((hs, ws))
                    dp[hs][ws] = dp[h][w] + 1
                # elif dp[hs][ws] <= dp[h][w]:
                #    break
                if hs == glh and ws == glw:
                    return dp[h][w] + 1
    return -1


def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin python3
# -*- coding: utf-8 -*-
 
H, W, K = map(int,input().split())
sth, stw, glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1
 
INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
 
from collections import deque
 
def bfs(sth, stw, glh, glw):
    next_q = deque([])
    next_q.append((sth,stw,0))
    Seen[sth][stw] = 0
 
    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, c = next_q.popleft()
        for dh, dw in direc:
            for sk in range(1,K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Seen[hs][ws]==INF:
                    next_q.append((hs,ws,c+1))
                    Seen[hs][ws] = c + 1
                elif Seen[hs][ws]<=c:
                    break
                if hs==glh and ws==glw:
                    return c + 1
    return -1

def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)

if __name__ == '__main__':
    main()

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

N_MAX = 200000 + 5
sys.setrecursionlimit(N_MAX)

H, W, K = map(int, sys.stdin.readline().split())
x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
INF = 10**6 * K

dp = [[INF for _ in range(W+2)] for _ in range(H+2)]

dp[0] = [-1]*(W+2)
dp[H+1] = [-1]*(W+2)
for h in range(1,H+1):
    s = sys.stdin.readline()
    dp[h][0] = -1
    dp[h][W+1] = -1
    for w in range(1,W+1):
        if s[w-1] == "@":
            dp[h][w] = -1

### BFS ###

# ステップ方向
D = [0, 1, 2, 3]  # direction
Y = [1, 0, -1, 0]
X = [0, 1, 0, -1]

def bfs(x1, y1, x2, y2):
    
    q = deque()
    q.append((x1, y1))

    while q:
        # print(q)
        x0, y0 = q.popleft()

        for x, y in zip(X, Y):

            for i in range(1,K+1):

                # print(y0,y,x0,x,d, (y0+y,x0+x,d), end=" : ")
                dp_c = dp[x0][y0]  # 現在のdp値
                n_x, n_y = x0+x*i, y0+y*i

                # print(dp_c, (n_x,n_y), end=" : ")

                if dp[n_x][n_y] == -1:
                    # print("@")
                    break

                if dp[n_x][n_y] == INF:
                    dp[n_x][n_y] = dp_c + 1
                elif dp[n_x][n_y] <= dp_c:
                    break

                if n_x == x2 and n_y == y2:
                    return dp[n_x][n_y]

                q.append((n_x, n_y))

    return -1

# スタート地点を 0 にする
dp[x1][y1] = 0

a = bfs(x1,y1,x2,y2)

print(a)

Fixed submission:
#!/usr/bin python3
# -*- coding: utf-8 -*-
 
H, W, K = map(int,input().split())
sth, stw, glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1
 
INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
 
from collections import deque
 
def bfs(sth, stw, glh, glw):
    next_q = deque([])
    next_q.append((sth,stw,0))
    Seen[sth][stw] = 0
 
    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, c = next_q.popleft()
        for dh, dw in direc:
            for sk in range(1,K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Seen[hs][ws]==INF:
                    next_q.append((hs,ws,c+1))
                    Seen[hs][ws] = c + 1
                elif Seen[hs][ws]<=c:
                    break
                if hs==glh and ws==glw:
                    return c + 1
    return -1

def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
from collections import deque
import math
import sys

N_MAX = 200000 + 5
sys.setrecursionlimit(N_MAX)

H, W, K = map(int, sys.stdin.readline().split())
x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
INF = 10**6 * K

dp = [[INF for _ in range(W+2)] for _ in range(H+2)]

dp[0] = [-1]*(W+2)
dp[H+1] = [-1]*(W+2)
for h in range(1,H+1):
    s = sys.stdin.readline()
    dp[h][0] = -1
    dp[h][W+1] = -1
    for w in range(1,W+1):
        if s[w-1] == "@":
            dp[h][w] = -1

### BFS ###

# ステップ方向
D = [0, 1, 2, 3]  # direction
Y = [1, 0, -1, 0]
X = [0, 1, 0, -1]

def bfs(x1, y1, x2, y2):
    
    q = deque()
    q.append((x1, y1))

    while q:
        # print(q)
        x0, y0 = q.popleft()

        for x, y in zip(X, Y):

            for i in range(1,K+1):

                # print(y0,y,x0,x,d, (y0+y,x0+x,d), end=" : ")
                dp_c = dp[x0][y0]  # 現在のdp値
                n_x, n_y = x0+x*i, y0+y*i

                # print(dp_c, (n_x,n_y), end=" : ")

                if dp[n_x][n_y] == -1:
                    # print("@")
                    break

                if dp[n_x][n_y] == INF:
                    dp[n_x][n_y] = c + 1
                elif dp[n_x][n_y] <= c:
                    break

                if n_x == x2 and n_y == y2:
                    return dp[n_x][n_y]

                q.append((n_x, n_y))

    return -1

# スタート地点を 0 にする
dp[x1][y1] = 0

a = bfs(x1,y1,x2,y2)

print(a)

Fixed submission:
#!/usr/bin python3
# -*- coding: utf-8 -*-
 
H, W, K = map(int,input().split())
sth, stw, glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1
 
INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
 
from collections import deque
 
def bfs(sth, stw, glh, glw):
    next_q = deque([])
    next_q.append((sth,stw,0))
    Seen[sth][stw] = 0
 
    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, c = next_q.popleft()
        for dh, dw in direc:
            for sk in range(1,K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Seen[hs][ws]==INF:
                    next_q.append((hs,ws,c+1))
                    Seen[hs][ws] = c + 1
                elif Seen[hs][ws]<=c:
                    break
                if hs==glh and ws==glw:
                    return c + 1
    return -1

def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)

if __name__ == '__main__':
    main()

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

N_MAX = 200000 + 5
sys.setrecursionlimit(N_MAX)

H, W, K = map(int, sys.stdin.readline().split())
x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
INF = 10**6 * K

dp = [[INF for _ in range(W+2)] for _ in range(H+2)]

dp[0] = [-1]*(W+2)
dp[H+1] = [-1]*(W+2)
for h in range(1,H+1):
    s = sys.stdin.readline()
    dp[h][0] = -1
    dp[h][W+1] = -1
    for w in range(1,W+1):
        if s[w-1] == "@":
            dp[h][w] = -1

### BFS ###

# ステップ方向
D = [0, 1, 2, 3]  # direction
Y = [1, 0, -1, 0]
X = [0, 1, 0, -1]

def bfs(x1, y1, x2, y2):
    
    q = deque()
    q.append((x1, y1))

    while q:
        # print(q)
        x0, y0 = q.popleft()

        for x, y in zip(X, Y):

            for i in range(1,K+1):

                # print(y0,y,x0,x,d, (y0+y,x0+x,d), end=" : ")
                dp_c = dp[x0][y0]  # 現在のdp値
                n_x, n_y = x0+x*i, y0+y*i

                # print(dp_c, (n_x,n_y), end=" : ")

                if dp[n_x][n_y] == -1:
                    # print("@")
                    break

                if dp[n_x][n_y] <= dp_c:
                    break

                dp[n_x][n_y] = dp_c + 1

                if n_x == x2 and n_y == y2:
                    return dp[n_x][n_y]
                q.append((n_x, n_y))

    return -1

# スタート地点を 0 にする
dp[x1][y1] = 0

a = bfs(x1,y1,x2,y2)

print(a)

Fixed submission:
#!/usr/bin python3
# -*- coding: utf-8 -*-
 
H, W, K = map(int,input().split())
sth, stw, glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1
 
INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
 
from collections import deque
 
def bfs(sth, stw, glh, glw):
    next_q = deque([])
    next_q.append((sth,stw,0))
    Seen[sth][stw] = 0
 
    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, c = next_q.popleft()
        for dh, dw in direc:
            for sk in range(1,K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Seen[hs][ws]==INF:
                    next_q.append((hs,ws,c+1))
                    Seen[hs][ws] = c + 1
                elif Seen[hs][ws]<=c:
                    break
                if hs==glh and ws==glw:
                    return c + 1
    return -1

def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)

if __name__ == '__main__':
    main()

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

N_MAX = 200000 + 5
sys.setrecursionlimit(N_MAX)

H, W, K = map(int, sys.stdin.readline().split())
x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
INF = 10**6 * K

dp = [[INF for _ in range(W+2)] for _ in range(H+2)]

dp[0] = [-1]*(W+2)
dp[H+1] = [-1]*(W+2)
for h in range(1,H+1):
    s = sys.stdin.readline()
    dp[h][0] = -1
    dp[h][W+1] = -1
    for w in range(1,W+1):
        if s[w-1] == "@":
            dp[h][w] = -1

### BFS ###

# ステップ方向
D = [0, 1, 2, 3]  # direction
Y = [1, 0, -1, 0]
X = [0, 1, 0, -1]

def bfs(x1, y1, x2, y2):
    
    q = deque()
    q.append((x1, y1))

    while q:
        # print(q)
        x0, y0 = q.popleft()

        for x, y in zip(X, Y):

            for i in range(1,K+1):

                # print(y0,y,x0,x,d, (y0+y,x0+x,d), end=" : ")
                dp_c = dp[x0][y0]  # 現在のdp値
                n_x, n_y = x0+x*i, y0+y*i

                # print(dp_c, (n_x,n_y), end=" : ")

                if dp[n_x][n_y] == -1:
                    # print("@")
                    break

                if dp[n_x][n_y] <= dp_c + 1:
                    continue

                dp[n_x][n_y] = dp_c + 1

                if n_x == x2 and n_y == y2:
                    return dp[n_x][n_y]
                q.append((n_x, n_y))

    return -1

# スタート地点を 0 にする
dp[x1][y1] = 0

a = bfs(x1,y1,x2,y2)

print(a)

Fixed submission:
#!/usr/bin python3
# -*- coding: utf-8 -*-
 
H, W, K = map(int,input().split())
sth, stw, glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1
 
INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
 
from collections import deque
 
def bfs(sth, stw, glh, glw):
    next_q = deque([])
    next_q.append((sth,stw,0))
    Seen[sth][stw] = 0
 
    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, c = next_q.popleft()
        for dh, dw in direc:
            for sk in range(1,K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Seen[hs][ws]==INF:
                    next_q.append((hs,ws,c+1))
                    Seen[hs][ws] = c + 1
                elif Seen[hs][ws]<=c:
                    break
                if hs==glh and ws==glw:
                    return c + 1
    return -1

def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)

if __name__ == '__main__':
    main()

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

N_MAX = 200000 + 5
sys.setrecursionlimit(N_MAX)

H, W, K = map(int, sys.stdin.readline().split())
x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
INF = 10**6 * K

dp = [[INF for _ in range(W+2)] for _ in range(H+2)]

dp[0] = [-1]*(W+2)
dp[H+1] = [-1]*(W+2)
for h in range(1,H+1):
    s = sys.stdin.readline()
    dp[h][0] = -1
    dp[h][W+1] = -1
    for w in range(1,W+1):
        if s[w-1] == "@":
            dp[h][w] = -1

### BFS ###

# ステップ方向
D = [0, 1, 2, 3]  # direction
Y = [1, 0, -1, 0]
X = [0, 1, 0, -1]

def bfs(x1, y1):
    
    q = deque()
    q.append((x1, y1))

    while q:
        # print(q)
        x0, y0 = q.popleft()

        for x, y in zip(X, Y):

            for i in range(1,K+1):

                # print(y0,y,x0,x,d, (y0+y,x0+x,d), end=" : ")
                dp_c = dp[x0][y0]  # 現在のdp値
                n_x, n_y = x0+x*i, y0+y*i

                # print(dp_c, (n_x,n_y), end=" : ")

                if dp[n_x][n_y] == -1:
                    # print("@")
                    break

                if dp[n_x][n_y] <= dp_c + 1:
                    continue

                dp[n_x][n_y] = dp_c + 1
                q.append((n_x, n_y))


# スタート地点を 0 にする
dp[x1][y1] = 0

bfs(x1,y1)

# print(dp)
# print(x2-1,y2-1)

if dp[x2][y2] == INF:
    print(-1)
else:
    print(dp[x2][y2])

Fixed submission:
#!/usr/bin python3
# -*- coding: utf-8 -*-
 
H, W, K = map(int,input().split())
sth, stw, glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1
 
INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
 
from collections import deque
 
def bfs(sth, stw, glh, glw):
    next_q = deque([])
    next_q.append((sth,stw,0))
    Seen[sth][stw] = 0
 
    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, c = next_q.popleft()
        for dh, dw in direc:
            for sk in range(1,K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Seen[hs][ws]==INF:
                    next_q.append((hs,ws,c+1))
                    Seen[hs][ws] = c + 1
                elif Seen[hs][ws]<=c:
                    break
                if hs==glh and ws==glw:
                    return c + 1
    return -1

def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)

if __name__ == '__main__':
    main()

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

N_MAX = 200000 + 5
sys.setrecursionlimit(N_MAX)

H, W, K = map(int, sys.stdin.readline().split())
x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
INF = 10**6 * K

dp = [[INF for _ in range(W)] for _ in range(H)]

for h in range(H):
    s = sys.stdin.readline()
    for w in range(W):
        if s[w] == "@":
            dp[h][w] = -1

### BFS ###

# ステップ方向
D = [0, 1, 2, 3]  # direction
Y = [1, 0, -1, 0]
X = [0, 1, 0, -1]

def bfs(x1, y1):
    
    q = deque()
    q.append((x1, y1))

    while q:
        # print(q)
        x0, y0 = q.popleft()

        for x, y in zip(X, Y):

            for i in range(1,K+1):

                # print(y0,y,x0,x,d, (y0+y,x0+x,d), end=" : ")
                dp_c = dp[x0][y0]  # 現在のdp値
                n_x, n_y = x0+x*i, y0+y*i

                # print(dp_c, (n_x,n_y), end=" : ")

                if (n_x)<0 or (n_x)>=H or (n_y)<0 or (n_y)>=W:
                    # print("out of range")
                    break

                if dp[n_x][n_y] == -1:
                    # print("@")
                    break

                if dp[n_x][n_y] <= dp_c + 1:
                    continue

                dp[n_x][n_y] = dp_c + 1
                q.append((n_x, n_y))


# スタート地点を 0 にする
dp[x1-1][y1-1] = 0

# print(x1-1,y1-1)
# print(dp)

bfs(x1-1,y1-1)

# print(dp)
# print(x2-1,y2-1)

if dp[x2 - 1][y2 - 1] == INF:
    print(-1)
else:
    print(dp[x2 - 1][y2 - 1])

Fixed submission:
#!/usr/bin python3
# -*- coding: utf-8 -*-
 
H, W, K = map(int,input().split())
sth, stw, glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1
 
INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
 
from collections import deque
 
def bfs(sth, stw, glh, glw):
    next_q = deque([])
    next_q.append((sth,stw,0))
    Seen[sth][stw] = 0
 
    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, c = next_q.popleft()
        for dh, dw in direc:
            for sk in range(1,K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Seen[hs][ws]==INF:
                    next_q.append((hs,ws,c+1))
                    Seen[hs][ws] = c + 1
                elif Seen[hs][ws]<=c:
                    break
                if hs==glh and ws==glw:
                    return c + 1
    return -1

def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)

if __name__ == '__main__':
    main()

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

N_MAX = 200000 + 5
sys.setrecursionlimit(N_MAX)

H, W, K = map(int, sys.stdin.readline().split())
x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
INF = 10**6 * K

dp = [[INF for _ in range(W)] for _ in range(H)]

for h in range(H):
    s = sys.stdin.readline()
    for w in range(W):
        if s[w] == "@":
            dp[h][w] = -1

### BFS ###

# ステップ方向
D = [0, 1, 2, 3]  # direction
Y = [1, 0, -1, 0]
X = [0, 1, 0, -1]

def bfs(x1, y1):
    
    q = deque()
    q.append((x1, y1))

    while q:
        # print(q)
        x0, y0 = q.popleft()

        for x, y in zip(X, Y):

            for i in range(1,K+1):

                # print(y0,y,x0,x,d, (y0+y,x0+x,d), end=" : ")
                dp_c = dp[x0][y0]  # 現在のdp値
                n_x, n_y = x0+x*i, y0+y*i

                # print(dp_c, (n_x,n_y), end=" : ")

                if (n_x)<0 or (n_x)>=H or (n_y)<0 or (n_y)>=W:
                    # print("out of range")
                    break

                if dp[n_x][n_y] == -1:
                    # print("@")
                    break

                if dp[n_x][n_y] <= dp_c + 1:
                    continue

                dp[n_x][n_y] = dp_c + 1
                q.append((n_x, n_y))


# スタート地点を 0 にする
dp[x1-1][y1-1] = 0

# print(x1-1,y1-1)
# print(dp)

bfs(x1-1,y1-1)

# print(dp)
# print(x2-1,y2-1)

if dp[x2 - 1][y2 - 1] == INF:
    print(-1)
else:
    print(dp[x2 - 1][y2 - 1])

Fixed submission:
#!/usr/bin python3
# -*- coding: utf-8 -*-
 
H, W, K = map(int,input().split())
sth, stw, glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1
 
INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
 
from collections import deque
 
def bfs(sth, stw, glh, glw):
    next_q = deque([])
    next_q.append((sth,stw,0))
    Seen[sth][stw] = 0
 
    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, c = next_q.popleft()
        for dh, dw in direc:
            for sk in range(1,K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Seen[hs][ws]==INF:
                    next_q.append((hs,ws,c+1))
                    Seen[hs][ws] = c + 1
                elif Seen[hs][ws]<=c:
                    break
                if hs==glh and ws==glw:
                    return c + 1
    return -1

def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)

if __name__ == '__main__':
    main()

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

N_MAX = 200000 + 5
sys.setrecursionlimit(N_MAX)

H, W, K = map(int, sys.stdin.readline().split())
x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
INF = 10**6 * K

dp = [[INF for _ in range(W)] for _ in range(H)]

for h in range(H):
    s = sys.stdin.readline()
    for w in range(W):
        if s[w] == "@":
            dp[h][w] = -1

### BFS ###

# ステップ方向
D = [0, 1, 2, 3]  # direction
Y = [1, 0, -1, 0]
X = [0, 1, 0, -1]

def bfs(x1, y1):
    
    q = deque()
    q.append((x1, y1, 0))
    q.append((x1, y1, 1))
    q.append((x1, y1, 2))
    q.append((x1, y1, 3))

    while q:
        # print(q)
        x0, y0, d0 = q.popleft()

        for x, y, d in zip(X, Y, D):

            # print(y0,y,x0,x,d, (y0+y,x0+x,d), end=" : ")
            dp_c = dp[x0][y0]  # 現在のdp値
            n_x, n_y = x0+x, y0+y

            # print(dp_c, (n_x,y0+y,d), end=" : ")

            if (n_x)<0 or (n_x)>=H or (n_y)<0 or (n_y)>=W:
                # print("out of range")
                continue

            if dp[n_x][n_y] == -1:
                # print("@")
                continue

            # 後ろを向いている場合
            if d % 4 == (d0+2)%4:
                # print("back")
                continue

            # 同方向を向いている場合
            if d % 4 == d0 % 4:
                if dp[n_x][n_y] <= dp_c + 1:
                    # print("not update / same d")
                    continue
                else:
                    dp[n_x][n_y] = dp_c + 1  # 更新

            # 90°方向を変えた場合
            elif d%4 == (d0+1)%4 or d%4 == (d0+3) % 4:
                if dp[n_x][n_y] <= K * math.ceil(dp_c/K) + 1:
                    # print("not update / 90")
                    continue
                else:
                    dp[n_x][n_y] = K * math.ceil(dp_c/K) + 1

            q.append((n_x, n_y, d))


# スタート地点を 0 にする
dp[x1-1][y1-1] = 0

# print(x1-1,y1-1)
# print(dp)

bfs(x1-1,y1-1)

# print(dp)
# print(x2-1,y2-1)

if dp[x2 - 1][y2 - 1] == INF:
    print(-1)
else:
    print(math.ceil(dp[x2 - 1][y2 - 1]/K))

Fixed submission:
#!/usr/bin python3
# -*- coding: utf-8 -*-
 
H, W, K = map(int,input().split())
sth, stw, glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1
 
INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
 
from collections import deque
 
def bfs(sth, stw, glh, glw):
    next_q = deque([])
    next_q.append((sth,stw,0))
    Seen[sth][stw] = 0
 
    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, c = next_q.popleft()
        for dh, dw in direc:
            for sk in range(1,K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Seen[hs][ws]==INF:
                    next_q.append((hs,ws,c+1))
                    Seen[hs][ws] = c + 1
                elif Seen[hs][ws]<=c:
                    break
                if hs==glh and ws==glw:
                    return c + 1
    return -1

def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)

if __name__ == '__main__':
    main()

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

N_MAX = 200000 + 5
sys.setrecursionlimit(N_MAX)

H, W, K = map(int, sys.stdin.readline().split())
x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
INF = 10**6 * K

dp = [[INF for _ in range(W)] for _ in range(H)]

for h in range(H):
    s = sys.stdin.readline()
    for w in range(W):
        if s[w] == "@":
            dp[h][w] = -1

### BFS ###

# ステップ方向
D = [0, 1, 2, 3]  # direction
Y = [1, 0, -1, 0]
X = [0, 1, 0, -1]

def bfs(x1, y1):
    
    q = deque()
    q.append((x1, y1, 0))
    q.append((x1, y1, 1))
    q.append((x1, y1, 2))
    q.append((x1, y1, 3))

    while q:
        # print(q)
        x0, y0, d0 = q.popleft()

        for x, y, d in zip(X, Y, D):

            # print(y0,y,x0,x,d, (y0+y,x0+x,d), end=" : ")
            dp_c = dp[x0][y0]  # 現在のdp値

            # print(dp_c, (x0+x,y0+y,d), end=" : ")

            if (x0+x)<0 or (x0+x)>=H or (y0+y)<0 or (y0+y)>=W:
                # print("out of range")
                continue

            if dp[x0+x][y0+y] == -1:
                # print("@")
                continue

            # 後ろを向いている場合
            if d % 4 == (d0+2)%4:
                # print("back")
                continue

            # 同方向を向いている場合
            if d % 4 == d0 % 4:
                if dp[x0+x][y0+y] <= dp_c + 1:
                    # print("not update / same d")
                    continue
                else:
                    dp[x0+x][y0+y] = dp_c + 1  # 更新

            # 90°方向を変えた場合
            elif d%4 == (d0+1)%4 or d%4 == (d0+3) % 4:
                if dp[x0+x][y0+y] <= K * math.ceil(dp_c/K) + 1:
                    # print("not update / 90")
                    continue
                else:
                    dp[x0+x][y0+y] = K * math.ceil(dp_c/K) + 1

            q.append((x0+x, y0+y, d))


# スタート地点を 0 にする
dp[x1-1][y1-1] = 0

# print(x1-1,y1-1)
# print(dp)

bfs(x1-1,y1-1)

# print(dp)
# print(x2-1,y2-1)

if dp[x2 - 1][y2 - 1] == INF:
    print(-1)
else:
    print(math.ceil(dp[x2 - 1][y2 - 1]/K))

Fixed submission:
#!/usr/bin python3
# -*- coding: utf-8 -*-
 
H, W, K = map(int,input().split())
sth, stw, glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1
 
INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
 
from collections import deque
 
def bfs(sth, stw, glh, glw):
    next_q = deque([])
    next_q.append((sth,stw,0))
    Seen[sth][stw] = 0
 
    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, c = next_q.popleft()
        for dh, dw in direc:
            for sk in range(1,K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Seen[hs][ws]==INF:
                    next_q.append((hs,ws,c+1))
                    Seen[hs][ws] = c + 1
                elif Seen[hs][ws]<=c:
                    break
                if hs==glh and ws==glw:
                    return c + 1
    return -1

def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)

if __name__ == '__main__':
    main()