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


def bfs(x1, y1, d):
    q = deque([])
    q.append((d, x1, y1))
    M[x1][y1] = d

    while q:
        d, x1, y1 = q.popleft()
        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                if x2 < 0 or x2 >= H:  # 枠外
                    break
                if y2 < 0 or y2 >= W:  # 枠外
                    break
                if m[x2][y2] == '@':  # 蓮の葉
                    break
                if M[x2][y2] < d + 1:  # より良い経路を探索済み。
                    break
                if M[x2][y2] == d + 1:  # 同等の良さの経路を探索済み。　飛び越えて次のマスを探索する。
                    continue

                q.append((d + 1, x2, y2))
                # M[x2][y2] = d + 1

    print(-1)


H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
xg -= 1
yg -= 1

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[float('inf')] * W for _ in range(H)]

bfs(xs - 1, ys - 1, 0)


Fixed submission:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])

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


def bfs(x1, y1, d):
    q = deque([])
    q.append((d, x1, y1))
    M[x1][y1] = d

    while q:
        d, x1, y1 = q.popleft()

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                if m[x2][y2] == '@':
                    break
                if x2 < 0 or x2 >= H:
                    break
                if y2 < 0 or y2 >= W:
                    break
                if M[x2][y2] < d + 1:
                    break
                if M[x2][y2] == d + 1:
                    continue

                q.append((d + 1, x2, y2))
                M[x2][y2] = d + 1

                # if (0 <= x2 < H) and (0 <= y2 < W):
                #     if m[x2][y2] == '@':
                #         break
                #     elif M[x2][y2] == -1:
                #         M[x2][y2] = d + 1
                #         q.append((d + 1, x2, y2))
                #     elif M[x2][y2] == d + 1:
                #         continue
                #     else:
                #         break
                # else:
                #     break
    print(-1)


H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
xg -= 1
yg -= 1

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for _ in range(H)]

bfs(xs - 1, ys - 1, 0)


Fixed submission:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])

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


def bfs(x1, y1, d):
    q = deque([])
    q.append((d, x1, y1))
    M[x1][y1] = d

    while q:
        d, x1, y1 = q.popleft()

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                # if m[x2][y2] == '@':
                #     break
                # if x2 < 0 or x2 >= H:
                #     break
                # if y2 < 0 or y2 >= W:
                #     break
                # if M[x2][y2] < d + 1:
                #     break
                # if M[x2][y2] == d + 1:
                #     continue

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        M[x2][y2] = d + 1
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] <= d:
                        break
                    elif M[x2][y2] == d + 1:
                        continue
                    else:
                        break
    print(-1)


H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
xg -= 1
yg -= 1

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for _ in range(H)]

bfs(xs - 1, ys - 1, 0)


Fixed submission:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])

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


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

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        # M[x2][y2] = d + 1
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] < d + 1:
                        break
                else:
                    break
    print(-1)


H, W, K = map(int, input().split())
xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(xs, ys, 0)

Fixed submission:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])

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


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

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] < d + 1:
                        break
                else:
                    break
    print(-1)


H, W, K = map(int, input().split())
xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(xs, ys, 0)


Fixed submission:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])

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


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

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                # if m[x2][y2] == '@':
                #     break
                # if x2 < 0 or x2 >= H:
                #     break
                # if y2 < 0 or y2 >= W:
                #     break
                # if M[x2][y2] < d + 1:
                #     break
                # if M[x2][y2] == d + 1:
                #     continue

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] <= d:
                        break
                    elif M[x2][y2] == d + 1:
                        continue
                    else:
                        break
    print(-1)


H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
xg -= 1
yg -= 1

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for _ in range(H)]

bfs(xs - 1, ys - 1, 0)


Fixed submission:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])

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


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

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] == d + 1:
                        continue
                    else:
                        break
                else:
                    break
    print(-1)


H, W, K = map(int, input().split())
xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(xs, ys, 0)


Fixed submission:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])

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


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

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                # if m[x2][y2] == '@':
                #     break
                # if x2 < 0 or x2 >= H:
                #     break
                # if y2 < 0 or y2 >= W:
                #     break
                # if M[x2][y2] < d + 1:
                #     break
                # if M[x2][y2] == d + 1:
                #     continue

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] == d + 1:
                        continue
                    else:
                        break

    print(-1)


# for i in range(len(M)):
#     print(M[i])


if __name__ == '__main__':
    H, W, K = map(int, sys.stdin.readline().strip().split())
    xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
    xg -= 1
    yg -= 1

    m = []
    for _ in range(H):
        m.append(list(map(str, sys.stdin.readline().strip())))

    M = [[-1] * W for _ in range(H)]

    bfs(xs - 1, ys - 1, 0)


Fixed submission:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])

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


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

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == "@":
                        break
                    elif M[x2][y2] == -1:
                        M[x2][y2] = d + 1
                        q.append((x2, y2, d + 1))  # 新しい点を足す。
                    elif M[x2][y2] < d + 1:
                        break
                else:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(xs, ys, 0)

print(M[xg][yg])


Fixed submission:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])

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


def bfs(xs, ys, d):
    queue = deque((xs, ys, d))
    M[xs][ys] = d
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        x1, y1, d = queue.popleft()  # queueに入っていたものを消す。
        if [x1, y1] == [xg, yg]:  # もしゴールについていたならば、そのときの手数を出す。
            return

        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == "@":
                        break
                    elif M[x2][y2] == -1:  # まだ来たことない点だったという条件
                        M[x2][y2] = d + 1
                        queue.append((x2, y2))  # 新しい点を足す。
                    elif M[x2][y2] < d + 1:
                        break
                else:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
xs, ys, xg, yg = map(int, input().split())
xs, ys, xg, yg = xs - 1, ys - 1, xg - 1, yg - 1

m = []
for i in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[-1] * W for i in range(H)]

bfs(xs, ys, 0)

print(M[xg][yg])


Fixed submission:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])

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


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

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                # if m[x2][y2] == '@':
                #     break
                # if x2 < 0 or x2 >= H:
                #     break
                # if y2 < 0 or y2 >= W:
                #     break
                # if M[x2][y2] < d + 1:
                #     break
                # if M[x2][y2] == d + 1:
                #     continue

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if m[x2][y2] == '@':
                        break
                    elif M[x2][y2] == -1:
                        q.append((d + 1, x2, y2))
                    elif M[x2][y2] == d + 1:
                        continue
                    else:
                        break

                    q.append((d + 1, x2, y2))
    print(-1)


# for i in range(len(M)):
#     print(M[i])


if __name__ == '__main__':
    H, W, K = map(int, sys.stdin.readline().strip().split())
    xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
    xg -= 1
    yg -= 1

    m = []
    for _ in range(H):
        m.append(list(map(str, sys.stdin.readline().strip())))

    M = [[-1] * W for _ in range(H)]

    bfs(xs - 1, ys - 1, 0)


Fixed submission:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])

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


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

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if [x1, y1] == [xg, yg]:
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                # if m[x2][y2] == '@':
                #     break
                # if x2 < 0 or x2 >= H:
                #     break
                # if y2 < 0 or y2 >= W:
                #     break
                # if M[x2][y2] < d + 1:
                #     break
                # if M[x2][y2] == d + 1:
                #     continue

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if (m[x2][y2] == '@') or (M[x2][y2] < d + 1):
                        break
                    elif M[x2][y2] == d + 1:
                        continue

                    q.append((d + 1, x2, y2))
    print(-1)


# for i in range(len(M)):
#     print(M[i])


if __name__ == '__main__':
    H, W, K = map(int, sys.stdin.readline().strip().split())
    xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
    xg -= 1
    yg -= 1

    m = []
    for _ in range(H):
        m.append(list(map(str, sys.stdin.readline().strip())))

    M = [[float('inf')] * W for _ in range(H)]

    bfs(xs - 1, ys - 1, 0)


Fixed submission:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])

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


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

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if (x1 == xg - 1) and (y1 == yg - 1):
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                # if m[x2][y2] == '@':
                #     break
                # if x2 < 0 or x2 >= H:
                #     break
                # if y2 < 0 or y2 >= W:
                #     break
                # if M[x2][y2] < d + 1:
                #     break
                # if M[x2][y2] == d + 1:
                #     continue

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if (m[x2][y2] == '@') or (M[x2][y2] < d + 1):
                        break
                    elif M[x2][y2] == d + 1:
                        continue

                    q.append((d + 1, x2, y2))
    print(-1)


# for i in range(len(M)):
#     print(M[i])


if __name__ == '__main__':
    H, W, K = map(int, sys.stdin.readline().strip().split())
    xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())

    m = []
    for _ in range(H):
        m.append(list(map(str, sys.stdin.readline().strip())))

    M = [[float('inf')] * W for _ in range(H)]

    bfs(xs - 1, ys - 1, 0)


Fixed submission:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])

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


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

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if (x1 == xg - 1) and (y1 == yg - 1):
            print(d)
            return

        for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                # if m[x2][y2] == '@':
                #     break
                # if x2 < 0 or x2 >= H:
                #     break
                # if y2 < 0 or y2 >= W:
                #     break
                # if M[x2][y2] < d + 1:
                #     break
                # if M[x2][y2] == d + 1:
                #     continue

                if (0 <= x2 < H) and (0 <= y2 < W):
                    if (m[x2][y2] == '@') or (M[x2][y2] < d + 1):
                        break
                    elif M[x2][y2] == d + 1:
                        continue

                    q.append((d + 1, x2, y2))
    print(-1)


# for i in range(len(M)):
#     print(M[i])


if __name__ == '__main__':
    H, W, K = map(int, sys.stdin.readline().strip().split())
    xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())

    m = []
    for _ in range(H):
        m.append(list(map(str, sys.stdin.readline().strip())))

    M = [[float('inf')] * W for _ in range(H)]

    bfs(xs - 1, ys - 1, 0)


Fixed submission:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])

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


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

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if (x1 == xg - 1) and (y1 == yg - 1):
            print(d)
            return
        
        for dx, dy in ([0, 1], [1, 0], [0, -1], [-1, 0]):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                if x2 < 0 or x2 >= H:
                    break
                if y2 < 0 or y2 >= W:
                    break
                if m[x2][y2] == '@':
                    break
                if M[x2][y2] < d + 1:
                    break
                if M[x2][y2] == d + 1:
                    continue

                q.append((d + 1, x2, y2))
    print(-1)


# if m[xs - 1][ys - 1] != '@':
#     bfs(xs - 1, ys - 1, 0)

# for i in range(len(M)):
#     print(M[i])


if __name__ == '__main__':
    H, W, K = map(int, sys.stdin.readline().strip().split())
    xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())

    m = []
    for _ in range(H):
        m.append(list(map(str, sys.stdin.readline().strip())))

    M = [[float('inf')] * W for _ in range(H)]
    
    bfs(xs - 1, ys - 1, 0)


Fixed submission:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])

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

H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[float('inf')] * W for _ in range(H)]


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

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if (x1 == xg - 1) and (y1 == yg - 1):
            break

        for dx, dy in ([0, 1], [1, 0], [0, -1], [-1, 0]):
            for k in range(1, K + 1):
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                if x2 < 0 or x2 >= H:
                    break
                if y2 < 0 or y2 >= W:
                    break
                if m[x2][y2] == '@':
                    break
                if M[x2][y2] < d + 1:
                    break
                if M[x2][y2] == d + 1:
                    continue

                q.append((d + 1, x2, y2))


if m[xs - 1][ys - 1] != '@':
    bfs(xs - 1, ys - 1, 0)

# for i in range(len(M)):
#     print(M[i])

ans = M[xg - 1][yg - 1]
if ans == float('inf'):
    print(-1)
else:
    print(ans)


Fixed submission:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])

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

H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[float('inf')] * W for _ in range(H)]


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

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if (x1 == xg - 1) and (y1 == yg - 1):
            break

        for dx, dy in ([0, 1], [1, 0], [0, -1], [-1, 0]):
            k = 1
            while k <= K:
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                if x2 < 0 or x2 >= H:
                    break
                if y2 < 0 or y2 >= W:
                    break
                if m[x2][y2] == '@':
                    break
                if M[x2][y2] < d + 1:
                    break
                if M[x2][y2] == d + 1:
                    continue

                q.append((d + 1, x2, y2))

                k += 1


if m[xs - 1][ys - 1] != '@':
    bfs(xs - 1, ys - 1, 0)

# for i in range(len(M)):
#     print(M[i])

ans = M[xg - 1][yg - 1]
if ans == float('inf'):
    print(-1)
else:
    print(ans)


Fixed submission:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])

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

H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[float('inf')] * W for _ in range(H)]


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

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if (x1 == xg - 1) and (y1 == yg - 1):
            break

        for dx, dy in ([0, 1], [1, 0], [0, -1], [-1, 0]):
            k = 1
            while k <= K:
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                if x2 < 0 or x2 >= H:
                    break
                if y2 < 0 or y2 >= W:
                    break
                if m[x2][y2] == '@':
                    break
                if M[x2][y2] < d + 1:
                    break
                if M[x2][y2] == d + 1:
                    continue

                q.append((d + 1, x2, y2))

                k += 1


if m[xs - 1][ys - 1] != '@':
    bfs(xs - 1, ys - 1, 0)

# for i in range(len(M)):
#     print(M[i])


ans = M[xg - 1][yg - 1]
if ans == float('inf'):
    print(-1)
else:
    print(ans)


Fixed submission:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])

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

H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[float('inf')] * W for _ in range(H)]


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

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if (x1 == xg - 1) and (y1 == yg - 1):
            break

        for dx, dy in ([0, 1], [1, 0], [0, -1], [-1, 0]):
            k = 1
            while k <= K:
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                if x2 < 0 or x2 >= H:
                    break
                if y2 < 0 or y2 >= W:
                    break
                if m[x2][y2] == '@':
                    break
                if M[x2][y2] < d + 1:
                    break

                q.append((d + 1, x2, y2))

                k += 1


if m[xs - 1][ys - 1] != '@':
    bfs(xs - 1, ys - 1, 0)

# for i in range(len(M)):
#     print(M[i])


ans = M[xg - 1][yg - 1]
if ans == float('inf'):
    print(-1)
else:
    print(ans)


Fixed submission:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])

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

H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[float('inf')] * W for _ in range(H)]


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

    while q:
        d, x1, y1 = q.popleft()

        M[x1][y1] = d

        if (x1 == xg - 1) and (y1 == yg - 1):
            break

        for dx, dy in ([0, 1], [1, 0], [0, -1], [-1, 0]):
            k = 1
            while k <= K:
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                if x2 < 0 or x2 >= H:
                    break
                if y2 < 0 or y2 >= W:
                    break
                if m[x2][y2] == '@':
                    break
                if M[x2][y2] < d + 1:
                    break

                q.append((d + 1, x2, y2))

                k += 1


if m[xs - 1][ys - 1] != '@':
    bfs(xs - 1, ys - 1, 0)

# for i in range(len(M)):
#     print(M[i])


ans = M[xg - 1][yg - 1]
if ans == float('inf'):
    print(-1)
else:
    print(ans)


Fixed submission:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq
from collections import deque
sys.setrecursionlimit(10 ** 8)
 
H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())
 
m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))
 
M = [[float('inf')] * W for _ in range(H)]
 
 
def bfs(x1, y1, d):
    q = deque()
    # heapq.heapify(q)
    # heapq.heappush(q, (d, (x1, y1)))
    q.append((d, (x1, y1)))
 
    while q:
        # d, u = heapq.heappop(q)
        d, u = q.popleft()
        x1 = u[0]
        y1 = u[1]
 
        M[x1][y1] = d
 
        if (x1 == xg - 1) and (y1 == yg - 1):
            break
 
        for dx, dy in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
            k = 1
            while k <= K:
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                if x2 < 0 or x2 >= H:
                    break
                if y2 < 0 or y2 >= W:
                    break
                if m[x2][y2] == '@':
                    break
                if M[x2][y2] != float('inf'):
                    break
 
                # heapq.heappush(q, (d + 1, (x2, y2)))
                q.append((d + 1, (x2, y2)))
 
                k += 1
 
 
if m[xs - 1][ys - 1] != '@':
    bfs(xs - 1, ys - 1, 0)
 
# for i in range(len(M)):
#     print(M[i])
 
 
ans = M[xg - 1][yg - 1]
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Fixed submission:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq
from collections import deque
sys.setrecursionlimit(10 ** 8)

H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[float('inf')] * W for _ in range(H)]


def bfs(x1, y1, d):
    q = deque()
    # heapq.heapify(q)
    # heapq.heappush(q, (d, (x1, y1)))
    q.append((d, (x1, y1)))

    while q:
        # d, u = heapq.heappop(q)
        d, u = q.popleft()
        x1 = u[0]
        y1 = u[1]

        M[x1][y1] = d

        if (x1 == xg - 1) and (y1 == yg - 1):
            break

        for dx, dy in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
            k = 1
            while k <= K:
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                if x2 < 0 or x2 >= H:
                    break
                if y2 < 0 or y2 >= W:
                    break
                if m[x2][y2] == '@':
                    break
                if M[x2][y2] != float('inf'):
                    break

                # heapq.heappush(q, (d + 1, (x2, y2)))
                q.append((d + 1, (x2, y2)))

                k += 1


if m[xs - 1][ys - 1] != '@':
    bfs(xs - 1, ys - 1, 0)

# for i in range(len(M)):
#     print(M[i])


ans = M[xg - 1][yg - 1]
if ans == float('inf'):
    print(-1)
else:
    print(ans)


Fixed submission:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq
sys.setrecursionlimit(10 ** 8)

H, W, K = map(int, sys.stdin.readline().strip().split())
xs, ys, xg, yg = map(int, sys.stdin.readline().strip().split())

m = []
for _ in range(H):
    m.append(list(map(str, sys.stdin.readline().strip())))

M = [[float('inf')] * W for _ in range(H)]


def bfs(x1, y1, d):
    q = []
    heapq.heapify(q)
    heapq.heappush(q, (d, (x1, y1)))

    while q:
        d, u = heapq.heappop(q)
        x1 = u[0]
        y1 = u[1]

        M[x1][y1] = d

        if (x1 == xg - 1) and (y1 == yg - 1):
            break

        for dx, dy in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
            k = 1
            while k <= K:
                x2 = x1 + dx * k
                y2 = y1 + dy * k
                if x2 < 0 or x2 >= H:
                    break
                if y2 < 0 or y2 >= W:
                    break
                if m[x2][y2] == '@':
                    break
                if M[x2][y2] != float('inf'):
                    break

                heapq.heappush(q, (d + 1, (x2, y2)))

                k += 1


if m[xs - 1][ys - 1] != '@':
    bfs(xs - 1, ys - 1, 0)

# for i in range(len(M)):
#     print(M[i])


ans = M[xg - 1][yg - 1]
if ans == float('inf'):
    print(-1)
else:
    print(ans)


Fixed submission:
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        # queueには訪れた地点が入っている。そこから、4方向に移動できるか考え、queueから消す。
        y, x = queue.popleft()  # queueに入っていたものを消す。
        if [y, x] == [gy, gx]:  # もしゴールについていたならば、そのときの手数を出す。
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            l = 1
            while True:
                new_y, new_x = y + j * l, x + k * l
                if (0 <= new_y < H) and (0 <= new_x < W):
                    if maze[new_y][new_x] == "@":
                        break
                    elif visited[new_y][new_x] == -1:  # まだ来たことない点だったという条件
                        visited[new_y][new_x] = visited[y][x] + 1
                        queue.append([new_y, new_x])  # 新しい点を足す。
                    elif visited[new_y][new_x] < visited[y][x] + 1:
                        break
                else:
                    break
                l += 1
                if l == K + 1:
                    break


H, W, K = map(int, input().split())
# K = min(K, max(H, W))
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1 - 1, y1 - 1, x2 - 1, y2 - 1
C = [0] * H
for i in range(H):
    C[i] = str(input())
visited = [[-1] * W for i in range(H)]
bfs(C, visited, x1, y1, x2, y2)
# print(visited)
print(visited[x2][y2])