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

def calc_cost(row, pt):
    return row*10**8 + pt

def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = [[1]*(w+2) for _ in range(h+2)]
    for i in range(1, h+1):
        s = input()
        for j in range(w):
            if s[j] == ".":
                pond[i][j+1] = 0
    hq = []
    heapq.heappush(hq, [calc_cost(1, 0), 1, 0, x1, y1, 0])
    heapq.heappush(hq, [calc_cost(1, 0), 1, 0, x1, y1, 1])
    heapq.heappush(hq, [calc_cost(1, 0), 1, 0, x1, y1, 2])
    heapq.heappush(hq, [calc_cost(1, 0), 1, 0, x1, y1, 3])
    ans = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    ans[x1][y1][0] = calc_cost(1, 0)
    ans[x1][y1][1] = calc_cost(1, 0)
    ans[x1][y1][2] = calc_cost(1, 0)
    ans[x1][y1][3] = calc_cost(1, 0)
    while len(hq) > 0:
        cost, row, pt, x, y, vec = heapq.heappop(hq)
        if cost > ans[x][y][vec]:
            continue
        for i in range(4):
            if vec == i:
                nx, ny = x, y
                if i == 0:
                    nx -= 1
                elif i == 1:
                    ny += 1
                elif i == 2:
                    nx += 1
                else:
                    ny -= 1
                if pond[nx][ny] == 1:
                    continue
                nrow, npt = row, pt
                if pt == k:
                    nrow += 1
                    npt = 1
                else:
                    npt += 1
                ncost = calc_cost(nrow, npt)
                if ncost < ans[nx][ny][i]:
                    heapq.heappush(hq, [ncost, nrow, npt, nx, ny, i])
                    ans[nx][ny][i] = ncost
            else:
                nrow, npt = row+1, 0
                ncost = calc_cost(nrow, npt)
                if ncost < ans[x][y][i]:
                    heapq.heappush(hq, [ncost, nrow, npt, x, y, i])
                    ans[x][y][i] = ncost
    tmp = float("inf")
    for i in range(4):
        if ans[x2][y2][i] // 10**8 < tmp:
            tmp = ans[x2][y2][i] // 10**8
    if tmp == float("inf"):
        print(-1)
    else:
        print(tmp)

if __name__ == "__main__":
    main()

Fixed submission:
import queue
import sys
input = sys.stdin.readline

def calc_next_point(x, y, vec, dist):
    if vec == 0:
        return x-dist, y
    elif vec == 1:
        return x, y+dist
    elif vec == 2:
        return x+dist, y
    else:
        return x, y-dist

def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = [[[-1]*4 for j in range(w+2)] for i in range(h+2)]
    for i in range(1, h+1):
        s = input()
        for j in range(w):
            if s[j] == ".":
                for l in range(4):
                    pond[i][j+1][l] = float("inf")
    qs = [queue.Queue(), queue.Queue()]
    for i in range(4):
        pond[x1][y1][i] = 0
        qs[0].put([0, x1, y1, i])
    p = 0
    minans = float("inf")
    g = False
    while not qs[0].empty() or not qs[1].empty():
        while not qs[p].empty():
            cost, x, y, vec = qs[p].get()
            np = (p+1)%2
            if cost >= minans:
                g = True
                break
            if x == x2 and y == y2:
                if cost < minans:
                    minans = cost
                g = True
                break
            for i in range(1, k+1):
                nx, ny = calc_next_point(x, y, vec, i)
                if pond[nx][ny][vec] == -1:
                    break
                ncost = cost + 1
                if pond[nx][ny][vec] < ncost:
                    break
                if pond[nx][ny][vec] == ncost:
                    continue
                pond[nx][ny][vec] = ncost
                if nx == x2 and ny == y2:
                    if ncost < minans:
                        minans = ncost
                    g = True
                    break
                for j in range(4):
                    if i == k:
                        if j != (vec+2)%4:
                            if j == vec or pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
                    elif i == 1:
                        if j != vec:
                            if j == (vec+2)%4 or pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
                    else:
                        if j != vec and j != (vec+2)%4:
                            if pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
            if g:
                break
        if g:
            break
        p = (p+1)%2
    if min(pond[x2][y2]) == float("inf"):
        print(-1)
    else:
        print(min(pond[x2][y2]))

if __name__ == "__main__":
    main()

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

def calc_cost(row, pt):
    return row*10**8 + pt

def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = [[1]*(w+2) for _ in range(h+2)]
    for i in range(1, h+1):
        s = input()
        for j in range(w):
            if s[j] == ".":
                pond[i][j+1] = 0
    hq = []
    heapq.heappush(hq, [calc_cost(1, 0), 1, 0, x1, y1, 0])
    heapq.heappush(hq, [calc_cost(1, 0), 1, 0, x1, y1, 1])
    heapq.heappush(hq, [calc_cost(1, 0), 1, 0, x1, y1, 2])
    heapq.heappush(hq, [calc_cost(1, 0), 1, 0, x1, y1, 3])
    ans = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    ans[x1][y1][0] = calc_cost(1, 0)
    ans[x1][y1][1] = calc_cost(1, 0)
    ans[x1][y1][2] = calc_cost(1, 0)
    ans[x1][y1][3] = calc_cost(1, 0)
    while len(hq) > 0:
        cost, row, pt, x, y, vec = heapq.heappop(hq)
        for i in range(4):
            if cost > ans[x][y][i]:
                continue
            nx, ny = x, y
            nrow, npt, = row, pt
            ncost = cost
            if i == 0:
                nx -= 1
            elif i == 1:
                ny += 1
            elif i == 2:
                nx += 1
            else:
                ny -= 1
            if pond[nx][ny] == 1:
                continue
            if i == vec:
                if pt == k:
                    nrow += 1
                    npt = 1
                else:
                    npt += 1
            else:
                npt = 1
                nrow += 1
            ncost = calc_cost(nrow, npt)
            if ncost < ans[nx][ny][i]:
                ans[nx][ny][i] = ncost
                heapq.heappush(hq, [ncost, nrow, npt, nx, ny, i])
    tmp = float("inf")
    for i in range(4):
        if ans[x2][y2][i] // 10**8 < tmp:
            tmp = ans[x2][y2][i] // 10**8
    if tmp == float("inf"):
        print(-1)
    else:
        print(tmp)

if __name__ == "__main__":
    main()

Fixed submission:
import queue
import sys
input = sys.stdin.readline

def calc_next_point(x, y, vec, dist):
    if vec == 0:
        return x-dist, y
    elif vec == 1:
        return x, y+dist
    elif vec == 2:
        return x+dist, y
    else:
        return x, y-dist

def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = [[[-1]*4 for j in range(w+2)] for i in range(h+2)]
    for i in range(1, h+1):
        s = input()
        for j in range(w):
            if s[j] == ".":
                for l in range(4):
                    pond[i][j+1][l] = float("inf")
    qs = [queue.Queue(), queue.Queue()]
    for i in range(4):
        pond[x1][y1][i] = 0
        qs[0].put([0, x1, y1, i])
    p = 0
    minans = float("inf")
    g = False
    while not qs[0].empty() or not qs[1].empty():
        while not qs[p].empty():
            cost, x, y, vec = qs[p].get()
            np = (p+1)%2
            if cost >= minans:
                g = True
                break
            if x == x2 and y == y2:
                if cost < minans:
                    minans = cost
                g = True
                break
            for i in range(1, k+1):
                nx, ny = calc_next_point(x, y, vec, i)
                if pond[nx][ny][vec] == -1:
                    break
                ncost = cost + 1
                if pond[nx][ny][vec] < ncost:
                    break
                if pond[nx][ny][vec] == ncost:
                    continue
                pond[nx][ny][vec] = ncost
                if nx == x2 and ny == y2:
                    if ncost < minans:
                        minans = ncost
                    g = True
                    break
                for j in range(4):
                    if i == k:
                        if j != (vec+2)%4:
                            if j == vec or pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
                    elif i == 1:
                        if j != vec:
                            if j == (vec+2)%4 or pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
                    else:
                        if j != vec and j != (vec+2)%4:
                            if pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
            if g:
                break
        if g:
            break
        p = (p+1)%2
    if min(pond[x2][y2]) == float("inf"):
        print(-1)
    else:
        print(min(pond[x2][y2]))

if __name__ == "__main__":
    main()

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

def calc_cost(row, pt):
    return row*10**8 + pt

def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = [[1]*(w+2) for _ in range(h+2)]
    for i in range(1, h+1):
        s = input()
        for j in range(w):
            if s[j] == ".":
                pond[i][j+1] = 0
    hq = []
    heapq.heappush(hq, [calc_cost(1, 0), 1, 0, x1, y1, 0])
    heapq.heappush(hq, [calc_cost(1, 0), 1, 0, x1, y1, 1])
    heapq.heappush(hq, [calc_cost(1, 0), 1, 0, x1, y1, 2])
    heapq.heappush(hq, [calc_cost(1, 0), 1, 0, x1, y1, 3])
    ans = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    ans[x1][y1][0] = calc_cost(1, 0)
    ans[x1][y1][1] = calc_cost(1, 0)
    ans[x1][y1][2] = calc_cost(1, 0)
    ans[x1][y1][3] = calc_cost(1, 0)
    while len(hq) > 0:
        cost, row, pt, x, y, vec = heapq.heappop(hq)
        for i in range(4):
            if cost > ans[x][y][i]:
                continue
            nx, ny = x, y
            nrow, npt, = row, pt
            ncost = cost
            if i == 0:
                nx -= 1
            elif i == 1:
                ny += 1
            elif i == 2:
                nx += 1
            else:
                ny -= 1
            if pond[nx][ny] == 1:
                continue
            if i == vec:
                if pt == k:
                    nrow += 1
                    npt = 1
                else:
                    npt += 1
            else:
                npt = 1
                nrow += 1
            ncost = calc_cost(nrow, npt)
            if ncost < ans[nx][ny][i]:
                ans[nx][ny][i] = ncost
                heapq.heappush(hq, [ncost, nrow, npt, nx, ny, i])
    tmp = float("inf")
    for i in range(4):
        if ans[x2][y2][i] // 10**8 < tmp:
            tmp = ans[x2][y2][i] // 10**8
    if tmp == float("inf"):
        print(-1)
    else:
        print(tmp)

if __name__ == "__main__":
    main()

Fixed submission:
import queue
import sys
input = sys.stdin.readline

def calc_next_point(x, y, vec, dist):
    if vec == 0:
        return x-dist, y
    elif vec == 1:
        return x, y+dist
    elif vec == 2:
        return x+dist, y
    else:
        return x, y-dist

def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = [[[-1]*4 for j in range(w+2)] for i in range(h+2)]
    for i in range(1, h+1):
        s = input()
        for j in range(w):
            if s[j] == ".":
                for l in range(4):
                    pond[i][j+1][l] = float("inf")
    qs = [queue.Queue(), queue.Queue()]
    for i in range(4):
        pond[x1][y1][i] = 0
        qs[0].put([0, x1, y1, i])
    p = 0
    minans = float("inf")
    g = False
    while not qs[0].empty() or not qs[1].empty():
        while not qs[p].empty():
            cost, x, y, vec = qs[p].get()
            np = (p+1)%2
            if cost >= minans:
                g = True
                break
            if x == x2 and y == y2:
                if cost < minans:
                    minans = cost
                g = True
                break
            for i in range(1, k+1):
                nx, ny = calc_next_point(x, y, vec, i)
                if pond[nx][ny][vec] == -1:
                    break
                ncost = cost + 1
                if pond[nx][ny][vec] < ncost:
                    break
                if pond[nx][ny][vec] == ncost:
                    continue
                pond[nx][ny][vec] = ncost
                if nx == x2 and ny == y2:
                    if ncost < minans:
                        minans = ncost
                    g = True
                    break
                for j in range(4):
                    if i == k:
                        if j != (vec+2)%4:
                            if j == vec or pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
                    elif i == 1:
                        if j != vec:
                            if j == (vec+2)%4 or pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
                    else:
                        if j != vec and j != (vec+2)%4:
                            if pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
            if g:
                break
        if g:
            break
        p = (p+1)%2
    if min(pond[x2][y2]) == float("inf"):
        print(-1)
    else:
        print(min(pond[x2][y2]))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = [[1]*(w+2) for _ in range(h+2)]
    for i in range(1, h+1):
        s = input()
        for j in range(w):
            if s[j] == ".":
                pond[i][j+1] = 0
    hq = [[0, (x1, y1)]]
    st = set()
    R = set()
    L = set()
    U = set()
    D = set()
    dic = {}
    dic[(x1, y1)] = 0
    ans = -1
    while len(hq) > 0:
        cost, p = heapq.heappop(hq)
        if p in st:
            continue
        else:
            st.add(p)
        x, y = p[0], p[1]
        if x == x2 and y == y2:
            ans = cost
            break
        c = cost + 1
        for i in range(1, k+1):
            np = (x-i, y)
            if np in D or np in st or pond[x-i][y] == 1:
                break
            if np in dic and dic[np] <= c:
                U.add(np)
                continue
            dic[np] = c
            heapq.heappush(hq, [c, (x-i, y)])
            U.add(np)
        for i in range(1, k+1):
            np = (x+i, y)
            if np in U or np in st or pond[x+i][y] == 1:
                break
            if np in dic and dic[np] <= c:
                D.add(np)
                continue
            dic[np] = c
            heapq.heappush(hq, [c, (x+i, y)])
            D.add(np)
        for i in range(1, k+1):
            np = (x, y-i)
            if np in R or np in st or pond[x][y-i] == 1:
                break
            if np in dic and dic[np] <= c:
                L.add(np)
                continue
            dic[np] = c
            heapq.heappush(hq, [c, (x, y-i)])
            L.add(np)
        for i in range(1, k+1):
            np = (x, y+i)
            if np in L or np in st or pond[x][y+i] == 1:
                break
            if np in dic and dic[np] <= c:
                R.add(np)
                continue
            dic[np] = c
            heapq.heappush(hq, [c, (x, y+i)])
            R.add(np)
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
import queue
import sys
input = sys.stdin.readline

def calc_next_point(x, y, vec, dist):
    if vec == 0:
        return x-dist, y
    elif vec == 1:
        return x, y+dist
    elif vec == 2:
        return x+dist, y
    else:
        return x, y-dist

def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = [[[-1]*4 for j in range(w+2)] for i in range(h+2)]
    for i in range(1, h+1):
        s = input()
        for j in range(w):
            if s[j] == ".":
                for l in range(4):
                    pond[i][j+1][l] = float("inf")
    qs = [queue.Queue(), queue.Queue()]
    for i in range(4):
        pond[x1][y1][i] = 0
        qs[0].put([0, x1, y1, i])
    p = 0
    minans = float("inf")
    g = False
    while not qs[0].empty() or not qs[1].empty():
        while not qs[p].empty():
            cost, x, y, vec = qs[p].get()
            np = (p+1)%2
            if cost >= minans:
                g = True
                break
            if x == x2 and y == y2:
                if cost < minans:
                    minans = cost
                g = True
                break
            for i in range(1, k+1):
                nx, ny = calc_next_point(x, y, vec, i)
                if pond[nx][ny][vec] == -1:
                    break
                ncost = cost + 1
                if pond[nx][ny][vec] < ncost:
                    break
                if pond[nx][ny][vec] == ncost:
                    continue
                pond[nx][ny][vec] = ncost
                if nx == x2 and ny == y2:
                    if ncost < minans:
                        minans = ncost
                    g = True
                    break
                for j in range(4):
                    if i == k:
                        if j != (vec+2)%4:
                            if j == vec or pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
                    elif i == 1:
                        if j != vec:
                            if j == (vec+2)%4 or pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
                    else:
                        if j != vec and j != (vec+2)%4:
                            if pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
            if g:
                break
        if g:
            break
        p = (p+1)%2
    if min(pond[x2][y2]) == float("inf"):
        print(-1)
    else:
        print(min(pond[x2][y2]))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = [[1]*(w+2) for _ in range(h+2)]
    for i in range(1, h+1):
        s = input()
        for j in range(w):
            if s[j] == ".":
                pond[i][j+1] = 0
    hq = [[0, (x1, y1)]]
    st = set()
    R = set()
    L = set()
    U = set()
    D = set()
    dic = {}
    dic[(x1, y1)] = 0
    ans = -1
    while len(hq) > 0:
        cost, p = heapq.heappop(hq)
        if p in st:
            continue
        else:
            st.add(p)
        x, y = p[0], p[1]
        if x == x2 and y == y2:
            ans = cost
            break
        c = cost + 1
        for i in range(1, k+1):
            np = (x-i, y)
            if np in D or np in st or pond[x-i][y] == 1:
                break
            if np in dic and dic[np] <= c:
                continue
            dic[np] = c
            heapq.heappush(hq, [c, (x-i, y)])
            U.add(np)
        for i in range(1, k+1):
            np = (x+i, y)
            if np in U or np in st or pond[x+i][y] == 1:
                break
            if np in dic and dic[np] <= c:
                continue
            dic[np] = c
            heapq.heappush(hq, [c, (x+i, y)])
            D.add(np)
        for i in range(1, k+1):
            np = (x, y-i)
            if np in R or np in st or pond[x][y-i] == 1:
                break
            if np in dic and dic[np] <= c:
                continue
            dic[np] = c
            heapq.heappush(hq, [c, (x, y-i)])
            L.add(np)
        for i in range(1, k+1):
            np = (x, y+i)
            if np in L or np in st or pond[x][y+i] == 1:
                break
            if np in dic and dic[np] <= c:
                continue
            dic[np] = c
            heapq.heappush(hq, [c, (x, y+i)])
            R.add(np)
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
import queue
import sys
input = sys.stdin.readline

def calc_next_point(x, y, vec, dist):
    if vec == 0:
        return x-dist, y
    elif vec == 1:
        return x, y+dist
    elif vec == 2:
        return x+dist, y
    else:
        return x, y-dist

def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = [[[-1]*4 for j in range(w+2)] for i in range(h+2)]
    for i in range(1, h+1):
        s = input()
        for j in range(w):
            if s[j] == ".":
                for l in range(4):
                    pond[i][j+1][l] = float("inf")
    qs = [queue.Queue(), queue.Queue()]
    for i in range(4):
        pond[x1][y1][i] = 0
        qs[0].put([0, x1, y1, i])
    p = 0
    minans = float("inf")
    g = False
    while not qs[0].empty() or not qs[1].empty():
        while not qs[p].empty():
            cost, x, y, vec = qs[p].get()
            np = (p+1)%2
            if cost >= minans:
                g = True
                break
            if x == x2 and y == y2:
                if cost < minans:
                    minans = cost
                g = True
                break
            for i in range(1, k+1):
                nx, ny = calc_next_point(x, y, vec, i)
                if pond[nx][ny][vec] == -1:
                    break
                ncost = cost + 1
                if pond[nx][ny][vec] < ncost:
                    break
                if pond[nx][ny][vec] == ncost:
                    continue
                pond[nx][ny][vec] = ncost
                if nx == x2 and ny == y2:
                    if ncost < minans:
                        minans = ncost
                    g = True
                    break
                for j in range(4):
                    if i == k:
                        if j != (vec+2)%4:
                            if j == vec or pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
                    elif i == 1:
                        if j != vec:
                            if j == (vec+2)%4 or pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
                    else:
                        if j != vec and j != (vec+2)%4:
                            if pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
            if g:
                break
        if g:
            break
        p = (p+1)%2
    if min(pond[x2][y2]) == float("inf"):
        print(-1)
    else:
        print(min(pond[x2][y2]))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = [[1]*(w+2) for _ in range(h+2)]
    for i in range(1, h+1):
        s = input()
        for j in range(w):
            if s[j] == ".":
                pond[i][j+1] = 0
    hq = [[0, (x1, y1)]]
    st = set()
    R = set()
    L = set()
    U = set()
    D = set()
    dic = {}
    dic[(x1, y1)] = 0
    ans = -1
    while len(hq) > 0:
        cost, p = heapq.heappop(hq)
        if p in st:
            continue
        else:
            st.add(p)
        x, y = p[0], p[1]
        if x == x2 and y == y2:
            ans = cost
            break
        c = cost + 1
        for i in range(1, k+1):
            np = (x-i, y)
            if np in D or np in st or pond[x-i][y] == 1:
                break
            if np in dic and dic[np] <= c:
                continue
            dic[np] = c
            heapq.heappush(hq, [c, (x-i, y)])
            U.add(np)
        for i in range(1, k+1):
            np = (x+i, y)
            if np in U or np in st or pond[x+i][y] == 1:
                break
            if np in dic and dic[np] <= c:
                continue
            dic[np] = c
            heapq.heappush(hq, [c, (x+i, y)])
            D.add(np)
        for i in range(1, k+1):
            np = (x, y-i)
            if np in R or np in st or pond[x][y-i] == 1:
                break
            if np in dic and dic[np] <= c:
                continue
            dic[np] = c
            heapq.heappush(hq, [c, (x, y-i)])
            L.add(np)
        for i in range(1, k+1):
            np = (x, y+i)
            if np in L or np in st or pond[x][y+i] == 1:
                break
            if np in dic and dic[np] <= c:
                continue
            dic[np] = c
            heapq.heappush(hq, [c, (x, y+i)])
            R.add(np)
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
import queue
import sys
input = sys.stdin.readline

def calc_next_point(x, y, vec, dist):
    if vec == 0:
        return x-dist, y
    elif vec == 1:
        return x, y+dist
    elif vec == 2:
        return x+dist, y
    else:
        return x, y-dist

def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = [[[-1]*4 for j in range(w+2)] for i in range(h+2)]
    for i in range(1, h+1):
        s = input()
        for j in range(w):
            if s[j] == ".":
                for l in range(4):
                    pond[i][j+1][l] = float("inf")
    qs = [queue.Queue(), queue.Queue()]
    for i in range(4):
        pond[x1][y1][i] = 0
        qs[0].put([0, x1, y1, i])
    p = 0
    minans = float("inf")
    g = False
    while not qs[0].empty() or not qs[1].empty():
        while not qs[p].empty():
            cost, x, y, vec = qs[p].get()
            np = (p+1)%2
            if cost >= minans:
                g = True
                break
            if x == x2 and y == y2:
                if cost < minans:
                    minans = cost
                g = True
                break
            for i in range(1, k+1):
                nx, ny = calc_next_point(x, y, vec, i)
                if pond[nx][ny][vec] == -1:
                    break
                ncost = cost + 1
                if pond[nx][ny][vec] < ncost:
                    break
                if pond[nx][ny][vec] == ncost:
                    continue
                pond[nx][ny][vec] = ncost
                if nx == x2 and ny == y2:
                    if ncost < minans:
                        minans = ncost
                    g = True
                    break
                for j in range(4):
                    if i == k:
                        if j != (vec+2)%4:
                            if j == vec or pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
                    elif i == 1:
                        if j != vec:
                            if j == (vec+2)%4 or pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
                    else:
                        if j != vec and j != (vec+2)%4:
                            if pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
            if g:
                break
        if g:
            break
        p = (p+1)%2
    if min(pond[x2][y2]) == float("inf"):
        print(-1)
    else:
        print(min(pond[x2][y2]))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = [[1]*(w+2) for _ in range(h+2)]
    for i in range(1, h+1):
        s = input()
        for j in range(w):
            if s[j] == ".":
                pond[i][j+1] = 0
    hq = [[0, (x1, y1)]]
    st = set()
    R = set()
    L = set()
    U = set()
    D = set()
    ans = -1
    while len(hq) > 0:
        cost, p = heapq.heappop(hq)
        if p in st:
            continue
        else:
            st.add(p)
        x, y = p[0], p[1]
        if x == x2 and y == y2:
            ans = cost
            break
        c = cost + 1
        for i in range(1, k+1):
            np = (x-i, y)
            if np in D or np in st or pond[x-i][y] == 1:
                break
            if np in U:
                continue
            heapq.heappush(hq, [c, (x-i, y)])
            U.add(np)
        for i in range(1, k+1):
            np = (x+i, y)
            if np in U or np in st or pond[x+i][y] == 1:
                break
            if np in D:
                continue
            heapq.heappush(hq, [c, (x+i, y)])
            D.add(np)
        for i in range(1, k+1):
            np = (x, y-i)
            if np in R or np in st or pond[x][y-i] == 1:
                break
            if np in L:
                continue
            heapq.heappush(hq, [c, (x, y-i)])
            L.add(np)
        for i in range(1, k+1):
            np = (x, y+i)
            if np in L or np in st or pond[x][y+i] == 1:
                break
            if np in R:
                continue
            heapq.heappush(hq, [c, (x, y+i)])
            R.add(np)
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
import queue
import sys
input = sys.stdin.readline

def calc_next_point(x, y, vec, dist):
    if vec == 0:
        return x-dist, y
    elif vec == 1:
        return x, y+dist
    elif vec == 2:
        return x+dist, y
    else:
        return x, y-dist

def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = [[[-1]*4 for j in range(w+2)] for i in range(h+2)]
    for i in range(1, h+1):
        s = input()
        for j in range(w):
            if s[j] == ".":
                for l in range(4):
                    pond[i][j+1][l] = float("inf")
    qs = [queue.Queue(), queue.Queue()]
    for i in range(4):
        pond[x1][y1][i] = 0
        qs[0].put([0, x1, y1, i])
    p = 0
    minans = float("inf")
    g = False
    while not qs[0].empty() or not qs[1].empty():
        while not qs[p].empty():
            cost, x, y, vec = qs[p].get()
            np = (p+1)%2
            if cost >= minans:
                g = True
                break
            if x == x2 and y == y2:
                if cost < minans:
                    minans = cost
                g = True
                break
            for i in range(1, k+1):
                nx, ny = calc_next_point(x, y, vec, i)
                if pond[nx][ny][vec] == -1:
                    break
                ncost = cost + 1
                if pond[nx][ny][vec] < ncost:
                    break
                if pond[nx][ny][vec] == ncost:
                    continue
                pond[nx][ny][vec] = ncost
                if nx == x2 and ny == y2:
                    if ncost < minans:
                        minans = ncost
                    g = True
                    break
                for j in range(4):
                    if i == k:
                        if j != (vec+2)%4:
                            if j == vec or pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
                    elif i == 1:
                        if j != vec:
                            if j == (vec+2)%4 or pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
                    else:
                        if j != vec and j != (vec+2)%4:
                            if pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
            if g:
                break
        if g:
            break
        p = (p+1)%2
    if min(pond[x2][y2]) == float("inf"):
        print(-1)
    else:
        print(min(pond[x2][y2]))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = [[1]*(w+2) for _ in range(h+2)]
    for i in range(1, h+1):
        s = input()
        for j in range(w):
            if s[j] == ".":
                pond[i][j+1] = 0
    hq = [[0, (x1, y1)]]
    st = set()
    R = set()
    L = set()
    U = set()
    D = set()
    ans = -1
    while len(hq) > 0:
        cost, p = heapq.heappop(hq)
        if p in st:
            continue
        else:
            st.add(p)
        x, y = p[0], p[1]
        if x == x2 and y == y2:
            ans = cost
            break
        c = cost + 1
        for i in range(1, k+1):
            np = (x-i, y)
            if np in D or np in st or pond[x-i][y] == 1:
                break
            heapq.heappush(hq, [c, (x-i, y)])
            U.add(np)
        for i in range(1, k+1):
            np = (x+i, y)
            if np in U or np in st or pond[x+i][y] == 1:
                break
            heapq.heappush(hq, [c, (x+i, y)])
            D.add(np)
        for i in range(1, k+1):
            np = (x, y-i)
            if np in R or np in st or pond[x][y-i] == 1:
                break
            heapq.heappush(hq, [c, (x, y-i)])
            L.add(np)
        for i in range(1, k+1):
            np = (x, y+i)
            if np in L or np in st or pond[x][y+i] == 1:
                break
            heapq.heappush(hq, [c, (x, y+i)])
            R.add(np)
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
import queue
import sys
input = sys.stdin.readline

def calc_next_point(x, y, vec, dist):
    if vec == 0:
        return x-dist, y
    elif vec == 1:
        return x, y+dist
    elif vec == 2:
        return x+dist, y
    else:
        return x, y-dist

def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = [[[-1]*4 for j in range(w+2)] for i in range(h+2)]
    for i in range(1, h+1):
        s = input()
        for j in range(w):
            if s[j] == ".":
                for l in range(4):
                    pond[i][j+1][l] = float("inf")
    qs = [queue.Queue(), queue.Queue()]
    for i in range(4):
        pond[x1][y1][i] = 0
        qs[0].put([0, x1, y1, i])
    p = 0
    minans = float("inf")
    g = False
    while not qs[0].empty() or not qs[1].empty():
        while not qs[p].empty():
            cost, x, y, vec = qs[p].get()
            np = (p+1)%2
            if cost >= minans:
                g = True
                break
            if x == x2 and y == y2:
                if cost < minans:
                    minans = cost
                g = True
                break
            for i in range(1, k+1):
                nx, ny = calc_next_point(x, y, vec, i)
                if pond[nx][ny][vec] == -1:
                    break
                ncost = cost + 1
                if pond[nx][ny][vec] < ncost:
                    break
                if pond[nx][ny][vec] == ncost:
                    continue
                pond[nx][ny][vec] = ncost
                if nx == x2 and ny == y2:
                    if ncost < minans:
                        minans = ncost
                    g = True
                    break
                for j in range(4):
                    if i == k:
                        if j != (vec+2)%4:
                            if j == vec or pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
                    elif i == 1:
                        if j != vec:
                            if j == (vec+2)%4 or pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
                    else:
                        if j != vec and j != (vec+2)%4:
                            if pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
            if g:
                break
        if g:
            break
        p = (p+1)%2
    if min(pond[x2][y2]) == float("inf"):
        print(-1)
    else:
        print(min(pond[x2][y2]))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = ["@" for _ in range(h+2)]
    for i in range(w+1):
        pond[0] += "@"
        pond[h+1] += "@"
    for i in range(1, h+1):
        s = input()
        pond[i] += s + "@"
    hq = [[0, (x1, y1)]]
    st = set()
    ans = -1
    while len(hq) > 0:
        cost, p = heapq.heappop(hq)
        if p in st:
            continue
        else:
            st.add(p)
        x, y = p[0], p[1]
        if x == x2 and y == y2:
            ans = cost
            break
        c = cost + 1
        for i in range(1, k+1):
            np = (x-i, y)
            if np in st or pond[x-i][y] == "@":
                break
            heapq.heappush(hq, [c, (x-i, y)])
        for i in range(1, k+1):
            np = (x+i, y)
            if np in st or pond[x+i][y] == "@":
                break
            heapq.heappush(hq, [c, (x+i, y)])
        for i in range(1, k+1):
            np = (x, y-i)
            if np in st or pond[x][y-i] == "@":
                break
            heapq.heappush(hq, [c, (x, y-i)])
        for i in range(1, k+1):
            np = (x, y+i)
            if np in st or pond[x][y+i] == "@":
                break
            heapq.heappush(hq, [c, (x, y+i)])
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
import queue
import sys
input = sys.stdin.readline

def calc_next_point(x, y, vec, dist):
    if vec == 0:
        return x-dist, y
    elif vec == 1:
        return x, y+dist
    elif vec == 2:
        return x+dist, y
    else:
        return x, y-dist

def main():
    h, w, k = map(int, input().split())
    x1, y1, x2, y2 = map(int, input().split())
    pond = [[[-1]*4 for j in range(w+2)] for i in range(h+2)]
    for i in range(1, h+1):
        s = input()
        for j in range(w):
            if s[j] == ".":
                for l in range(4):
                    pond[i][j+1][l] = float("inf")
    qs = [queue.Queue(), queue.Queue()]
    for i in range(4):
        pond[x1][y1][i] = 0
        qs[0].put([0, x1, y1, i])
    p = 0
    minans = float("inf")
    g = False
    while not qs[0].empty() or not qs[1].empty():
        while not qs[p].empty():
            cost, x, y, vec = qs[p].get()
            np = (p+1)%2
            if cost >= minans:
                g = True
                break
            if x == x2 and y == y2:
                if cost < minans:
                    minans = cost
                g = True
                break
            for i in range(1, k+1):
                nx, ny = calc_next_point(x, y, vec, i)
                if pond[nx][ny][vec] == -1:
                    break
                ncost = cost + 1
                if pond[nx][ny][vec] < ncost:
                    break
                if pond[nx][ny][vec] == ncost:
                    continue
                pond[nx][ny][vec] = ncost
                if nx == x2 and ny == y2:
                    if ncost < minans:
                        minans = ncost
                    g = True
                    break
                for j in range(4):
                    if i == k:
                        if j != (vec+2)%4:
                            if j == vec or pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
                    elif i == 1:
                        if j != vec:
                            if j == (vec+2)%4 or pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
                    else:
                        if j != vec and j != (vec+2)%4:
                            if pond[nx][ny][j] > ncost:
                                pond[nx][ny][j] = ncost
                                qs[np].put([ncost, nx, ny, j])
            if g:
                break
        if g:
            break
        p = (p+1)%2
    if min(pond[x2][y2]) == float("inf"):
        print(-1)
    else:
        print(min(pond[x2][y2]))

if __name__ == "__main__":
    main()