Buggy python submission (verdict: Time Limit Exceeded):
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:
                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
                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()


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 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:
                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
                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
        p = (p+1)%2
    if min(pond[x2][y2]) == float("inf"):
        print(-1)
    else:
        print(min(pond[x2][y2]))

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 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:
                break
            if x == x2 and y == y2:
                if cost < minans:
                    minans = cost
                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
                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
        p = (p+1)%2
    if min(pond[x2][y2]) == float("inf"):
        print(-1)
    else:
        print(min(pond[x2][y2]))

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 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")
    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:
                break
            if x == x2 and y == y2:
                if cost < minans:
                    minans = cost
                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
                pond[nx][ny][vec] = ncost
                if nx == x2 and ny == y2:
                    if ncost < minans:
                        minans = ncost
                    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])
        p = (p+1)%2
    if min(pond[x2][y2]) == float("inf"):
        print(-1)
    else:
        print(min(pond[x2][y2]))

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 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")
    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:
                break
            if x == x2 and y == y2:
                if cost < minans:
                    minans = cost
                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
                pond[nx][ny][vec] = ncost
                if nx == x2 and ny == y2:
                    if ncost < minans:
                        minans = ncost
                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])
        p = (p+1)%2
    if min(pond[x2][y2]) == float("inf"):
        print(-1)
    else:
        print(min(pond[x2][y2]))

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 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")
    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:
                break
            if x == x2 and y == y2:
                if cost < minans:
                    minans = cost
            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
                pond[nx][ny][vec] = ncost
                if nx == x2 and ny == y2:
                    if ncost < minans:
                        minans = ncost
                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])
        p = (p+1)%2
    if min(pond[x2][y2]) == float("inf"):
        print(-1)
    else:
        print(min(pond[x2][y2]))

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 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")
    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:
                break
            if x == x2 and y == y2:
                if cost < minans:
                    minans = cost
            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
                pond[nx][ny][vec] = ncost
                if nx == x2 and ny == y2:
                    if ncost < minans:
                        minans = ncost
                for j in range(4):
                    if pond[nx][ny][j] > ncost or i == k:
                        pond[nx][ny][j] = ncost
                        qs[np].put([ncost, nx, ny, j])
        p = (p+1)%2
    if min(pond[x2][y2]) == float("inf"):
        print(-1)
    else:
        print(min(pond[x2][y2]))

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 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")
    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:
                break
            if x == x2 and y == y2:
                if cost < minans:
                    minans = cost
            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
                pond[nx][ny][vec] = ncost
                if nx == x2 and ny == y2:
                    if ncost < minans:
                        minans = ncost
                for j in range(4):
                    if i == k or j != vec:
                        if pond[nx][ny][j] >= ncost:
                            pond[nx][ny][j] = ncost
                            qs[np].put([ncost, nx, ny, j])
        p = (p+1)%2
    if min(pond[x2][y2]) == float("inf"):
        print(-1)
    else:
        print(min(pond[x2][y2]))

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 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
    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
            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
                pond[nx][ny][vec] = ncost
                for j in range(4):
                    if i == k or j != vec:
                        if pond[nx][ny][j] >= ncost:
                            pond[nx][ny][j] = ncost
                            qs[np].put([ncost, nx, ny, j])
        p = (p+1)%2
    if min(pond[x2][y2]) == float("inf"):
        print(-1)
    else:
        print(min(pond[x2][y2]))

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 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 = [[[False]*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] = True
    qs = [queue.Queue(), queue.Queue()]
    for i in range(4):
        pond[x1][y1][i] = False
        qs[0].put([0, x1, y1, i])
    ans = [float("inf")]*4
    p = 0
    while not qs[0].empty() or not qs[1].empty():
        while not qs[p].empty():
            cost, x, y, vec = qs[p].get()
            if x == x2 and y == y2 and ans[vec] > cost:
                ans[vec] = cost
            for i in range(1, k+1):
                nx, ny = calc_next_point(x, y, vec, i)
                if not pond[nx][ny][vec]:
                    break
                ncost = cost + 1
                np = (p+1)%2
                if nx == x2 and ny == y2 and ans[vec] > ncost:
                    ans[vec] = ncost
                for j in range(4):
                    if i == k or j != vec:
                        mx, my = calc_next_point(nx, ny, j, 0)
                        if pond[mx][my][j]:
                            qs[np].put([ncost, mx, my, j])
                            pond[mx][my][j] = False
                pond[nx][ny][vec] = False
        p = (p+1)%2
    if min(ans) == float("inf"):
        print(-1)
    else:
        print(min(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 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 = [[[False]*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] = True
    qs = [queue.Queue(), queue.Queue()]
    for i in range(4):
        pond[x1][y1][i] = False
        qs[0].put([0, x1, y1, i])
    ans = [float("inf")]*4
    p = 0
    while not qs[0].empty() or not qs[1].empty():
        while not qs[p].empty():
            cost, x, y, vec = qs[p].get()
            if x == x2 and y == y2 and ans[vec] > cost:
                ans[vec] = cost
            for i in range(1, k+1):
                nx, ny = calc_next_point(x, y, vec, i)
                if not pond[nx][ny][vec]:
                    break
                ncost = cost + 1
                np = (p+1)%2
                if nx == x2 and ny == y2 and ans[vec] > ncost:
                    ans[vec] = ncost
                for j in range(4):
                    if i == k or j != vec:
                        mx, my = calc_next_point(nx, ny, j, 0)
                        if pond[mx][my][j]:
                            qs[np].put([ncost, mx, my, j])
                pond[nx][ny][vec] = False
        p = (p+1)%2
    if min(ans) == float("inf"):
        print(-1)
    else:
        print(min(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 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]*(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
    q = queue.Queue()
    row = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    fs = [[[True]*4 for j in range(w+2)] for i in range(h+2)]
    rng = [i for i in range(k)]
    for i in range(4):
        row[x1][y1][i] = 0
        fs[x1][y1][i] = False
        nx, ny = calc_next_point(x1, y1, i, 1)
        if pond[nx][ny] == 0:
            row[nx][ny][i] == 1
            fs[nx][ny][i] = False
            q.put([1, nx, ny, i])
    while not q.empty():
        cost, x, y, vec = q.get()
        if x == x2 and y == y2:
            break
        for i in rng:
            nx, ny = calc_next_point(x, y, vec, i)
            if pond[nx][ny] == 1:
                break
            if row[nx][ny][vec] > cost:
                row[nx][ny][vec] = cost
            fs[nx][ny][vec] = False
            for j in range(4):
                mx, my = calc_next_point(nx, ny, j, 1)
                if pond[mx][my] == 1:
                    continue
                if row[mx][my][j] <= cost+1:
                    continue
                if i < k-1 and j == vec:
                    continue
                if row[mx][my][j] > cost+1 and fs[mx][my][j] :
                    row[mx][my][j] = cost+1
                    fs[mx][my][j] = False
                    q.put([cost+1, mx, my, j])
    ans = min(row[x2][y2])
    if ans == float("inf"):
        print(-1)
    else:
        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 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]*(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
    q = queue.Queue()
    row = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    fs = [[[True]*4 for j in range(w+2)] for i in range(h+2)]
    for i in range(4):
        row[x1][y1][i] = 0
        fs[x1][y1][i] = False
        nx, ny = calc_next_point(x1, y1, i, 1)
        if pond[nx][ny] == 0:
            row[nx][ny][i] == 1
            fs[nx][ny][i] = False
            q.put([1, nx, ny, i])
    while not q.empty():
        cost, x, y, vec = q.get()
        if x == x2 and y == y2:
            break
        i = 0
        while i < k:
            nx, ny = calc_next_point(x, y, vec, i)
            if pond[nx][ny] == 1:
                break
            if row[nx][ny][vec] > cost:
                row[nx][ny][vec] = cost
            fs[nx][ny][vec] = False
            for j in range(4):
                mx, my = calc_next_point(nx, ny, j, 1)
                if pond[mx][my] == 1:
                    continue
                if row[mx][my][j] <= cost+1:
                    continue
                if i < k-1 and j == vec:
                    continue
                if row[mx][my][j] > cost+1 and fs[mx][my][j] :
                    row[mx][my][j] = cost+1
                    fs[mx][my][j] = False
                    q.put([cost+1, mx, my, j])
            i += 1
    ans = min(row[x2][y2])
    if ans == float("inf"):
        print(-1)
    else:
        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 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]*(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
    q = queue.Queue()
    row = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    fs = [[[True]*4 for j in range(w+2)] for i in range(h+2)]
    for i in range(4):
        row[x1][y1][i] = 0
        fs[x1][y1][i] = False
        nx, ny = calc_next_point(x1, y1, i, 1)
        if pond[nx][ny] == 0:
            row[nx][ny][i] == 1
            fs[nx][ny][i] = False
            q.put([1, nx, ny, i])
    while not q.empty():
        cost, x, y, vec = q.get()
        if x == x2 and y == y2:
            break
        for i in range(k):
            nx, ny = calc_next_point(x, y, vec, i)
            if pond[nx][ny] == 1:
                break
            if row[nx][ny][vec] > cost:
                row[nx][ny][vec] = cost
            fs[nx][ny][vec] = False
            for j in range(4):
                mx, my = calc_next_point(nx, ny, j, 1)
                if pond[mx][my] == 1:
                    continue
                if row[mx][my][j] <= cost+1:
                    continue
                if i < k-1 and j == vec:
                    continue
                if row[mx][my][j] > cost+1 and fs[mx][my][j] :
                    row[mx][my][j] = cost+1
                    fs[mx][my][j] = False
                    q.put([cost+1, mx, my, j])
    ans = min(row[x2][y2])
    if ans == float("inf"):
        print(-1)
    else:
        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 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]*(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
    q = queue.Queue()
    row = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    for i in range(4):
        row[x1][y1][i] = 0
        nx, ny = calc_next_point(x1, y1, i, 1)
        if pond[nx][ny] == 0:
            row[nx][ny][i] == 1
            q.put([1, nx, ny, i])
    while not q.empty():
        cost, x, y, vec = q.get()
        if x == x2 and y == y2:
            break
        for i in range(k):
            nx, ny = calc_next_point(x, y, vec, i)
            if pond[nx][ny] == 1:
                break
            if row[nx][ny][vec] > cost:
                row[nx][ny][vec] = cost
            for j in range(4):
                mx, my = calc_next_point(nx, ny, j, 1)
                if pond[mx][my] == 1:
                    continue
                if row[mx][my][j] <= cost+1:
                    continue
                if i < k-1 and j == vec:
                    continue
                if row[mx][my][j] > cost+1:
                    row[mx][my][j] = cost+1
                    q.put([cost+1, mx, my, j])
    ans = min(row[x2][y2])
    if ans == float("inf"):
        print(-1)
    else:
        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 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]*(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
    q = queue.Queue()
    row = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    for i in range(4):
        row[x1][y1][i] = 0
        nx, ny = calc_next_point(x1, y1, i, 1)
        if pond[nx][ny] == 0:
            row[nx][ny][i] == 1
            q.put([1, nx, ny, i])
    while not q.empty():
        cost, x, y, vec = q.get()
        for i in range(k):
            nx, ny = calc_next_point(x, y, vec, i)
            if pond[nx][ny] == 1:
                break
            row[nx][ny][vec] = cost
            for j in range(4):
                mx, my = calc_next_point(nx, ny, j, 1)
                if pond[mx][my] == 1:
                    continue
                if row[mx][my][j] <= cost+1:
                    continue
                if i < k-1 and j == vec:
                    continue
                if row[mx][my][j] > cost+1:
                    row[mx][my][j] = cost+1
                    q.put([cost+1, mx, my, j])
    ans = min(row[x2][y2])
    if ans == float("inf"):
        print(-1)
    else:
        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 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]*(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
    q = queue.Queue()
    row = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    for i in range(4):
        row[x1][y1][i] = 0
        nx, ny = calc_next_point(x1, y1, i, 1)
        if pond[nx][ny] == 0:
            row[nx][ny][i] == 1
            q.put([1, nx, ny, i])
    while not q.empty():
        cost, x, y, vec = q.get()
        for i in range(k):
            nx, ny = calc_next_point(x, y, vec, i)
            if pond[nx][ny] == 1:
                break
            row[nx][ny][vec] = cost
            for j in range(4):
                mx, my = calc_next_point(nx, ny, j, 1)
                if pond[mx][my] == 1:
                    continue
                if i < k-1 and j == vec:
                    continue
                if row[mx][my][j] > cost+1:
                    row[mx][my][j] = cost+1
                    q.put([cost+1, mx, my, j])
    ans = min(row[x2][y2])
    if ans == float("inf"):
        print(-1)
    else:
        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 queue
import sys
input = sys.stdin.readline

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
    q = queue.Queue()
    row = [[float("inf")]*(w+2) for _ in range(h+2)]
    row[x1][y1] = 0
    ans = -1
    for i in range(4):
        q.put([0, x1, y1, i])
    while not q.empty():
        cost, x, y, vec = q.get()
        if cost > row[x][y]:
            continue
        if x == x2 and y == y2:
            ans = cost
            break
        i = 1
        while i <= k:
            nx, ny = x, y
            if vec == 0:
                nx -= i
            elif vec == 1:
                ny += i
            elif vec == 2:
                nx += i
            else:
                ny -= i
            if pond[nx][ny] == 1 or row[nx][ny] < cost + 1:
                break
            row[nx][ny] = cost + 1
            if i < k:
                for j in range(4):
                    if j != vec:
                        row[nx][ny] = cost+1
                        q.put([cost+1, nx, ny, j])
            else:
                for j in range(4):
                    row[nx][ny] = cost+1
                    q.put([cost+1, nx, ny, j])
            i += 1
    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
import sys
input = sys.stdin.readline

def update(x, y, k, cost, pt, vec, pond, row, hq, fs):
    hpush = heapq.heappush
    i = 1
    while True:
        nx, ny = x, y
        nc = cost + (i+k-1)//k
        if vec == 0:
            nx -= i
        elif vec == 1:
            ny += i
        elif vec == 2:
            nx += i
        else:
            ny -= i
        if pond[nx][ny] == 1:
            return
        if row[nx][ny][vec] > nc:
            row[nx][ny][vec] = nc
            if i == k:
                hpush(hq, [nc, nx, ny, i, vec])
            if fs[nx][ny]:
                for j in range(1, 4):
                    if row[nx][ny][(vec+j)%4] > nc:
                        row[nx][ny][(vec+j)%4] = nc
                        hpush(hq, [nc, nx, ny, k, (vec+j)%4])
                fs[nx][ny] = False
        else:
            return
        i += 1

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 = []
    row = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    fs = [[True]*(w+2) for _ in range(h+2)]
    hpop = heapq.heappop
    for i in range(4):
        row[x1][y1][i] = 0
        heapq.heappush(hq, [0, x1, y1, k, i])
    while len(hq) > 0:
        cost, x, y, pt, vec = hpop(hq)
        if cost > row[x][y][vec]:
            continue
        if x == x2 and y == y2:
            break
        update(x, y, k, cost, pt, vec, pond, row, hq, fs)
    ans = min(row[x2][y2])
    if ans == float("inf"):
        print(-1)
    else:
        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 queue
import sys
input = sys.stdin.readline

def update(x, y, k, cost, pt, vec, pond, row, q, fs):
    i = 1
    while True:
        nx, ny = x, y
        nc = cost + (i+k-1)//k
        if vec == 0:
            nx -= i
        elif vec == 1:
            ny += i
        elif vec == 2:
            nx += i
        else:
            ny -= i
        if pond[nx][ny] == 1:
            return
        if row[nx][ny][vec] > nc:
            row[nx][ny][vec] = nc
            if i == k:
                q.put([nc, nx, ny, i, vec])
            if fs[nx][ny]:
                for j in range(1, 4):
                    if row[nx][ny][(vec+j)%4] > nc:
                        row[nx][ny][(vec+j)%4] = nc
                        q.put([nc, nx, ny, k, (vec+j)%4])
                fs[nx][ny] = False
        else:
            return
        i += 1

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
    q = queue.Queue()
    row = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    fs = [[True]*(w+2) for _ in range(h+2)]
    for i in range(4):
        row[x1][y1][i] = 0
        q.put([0, x1, y1, k, i])
    while not q.empty():
        cost, x, y, pt, vec = q.get()
        if cost > row[x][y][vec]:
            continue
        update(x, y, k, cost, pt, vec, pond, row, q, fs)
    ans = min(row[x2][y2])
    if ans == float("inf"):
        print(-1)
    else:
        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
import sys
input = sys.stdin.readline

def update(x, y, k, cost, pt, vec, pond, row, hq, fs):
    hpush = heapq.heappush
    i = 1
    while i <= k:
        nx, ny = x, y
        nc = cost+1
        if vec == 0:
            nx -= i
        elif vec == 1:
            ny += i
        elif vec == 2:
            nx += i
        else:
            ny -= i
        if pond[nx][ny] == 1:
            return
        if row[nx][ny][vec] > nc:
            row[nx][ny][vec] = nc
            if i == k:
                hpush(hq, [nc, nx, ny, i, vec])
            if fs[nx][ny]:
                for j in range(1, 4):
                    if row[nx][ny][(vec+j)%4] > nc:
                        row[nx][ny][(vec+j)%4] = nc
                        hpush(hq, [nc, nx, ny, k, (vec+j)%4])
                fs[nx][ny] = False
        else:
            return
        i += 1

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 = []
    row = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    fs = [[True]*(w+2) for _ in range(h+2)]
    hpop = heapq.heappop
    for i in range(4):
        row[x1][y1][i] = 0
        heapq.heappush(hq, [0, x1, y1, k, i])
    while len(hq) > 0:
        cost, x, y, pt, vec = hpop(hq)
        if cost > row[x][y][vec]:
            continue
        update(x, y, k, cost, pt, vec, pond, row, hq, fs)
    ans = min(row[x2][y2])
    if ans == float("inf"):
        print(-1)
    else:
        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 queue
import sys
input = sys.stdin.readline

def update(x, y, k, cost, pt, vec, pond, row, q, fs):
    i = 1
    while i <= k:
        nx, ny = x, y
        nc = cost+1
        if vec == 0:
            nx -= i
        elif vec == 1:
            ny += i
        elif vec == 2:
            nx += i
        else:
            ny -= i
        if pond[nx][ny] == 1:
            return
        if row[nx][ny][vec] > nc:
            row[nx][ny][vec] = nc
            if i == k:
                q.put([nc, nx, ny, i, vec])
            if fs[nx][ny]:
                for j in range(1, 4):
                    if row[nx][ny][(vec+j)%4] > nc:
                        row[nx][ny][(vec+j)%4] = nc
                        q.put([nc, nx, ny, k, (vec+j)%4])
                fs[nx][ny] = False
        else:
            return
        i += 1

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
    q = queue.Queue()
    row = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    fs = [[True]*(w+2) for _ in range(h+2)]
    for i in range(4):
        row[x1][y1][i] = 0
        q.put([0, x1, y1, k, i])
    while not q.empty():
        cost, x, y, pt, vec = q.get()
        if cost > row[x][y][vec]:
            continue
        update(x, y, k, cost, pt, vec, pond, row, q, fs)
    ans = min(row[x2][y2])
    if ans == float("inf"):
        print(-1)
    else:
        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 queue
import sys
input = sys.stdin.readline

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
    q = queue.Queue()
    row = [[float("inf")]*(w+2) for _ in range(h+2)]
    row[x1][y1] = 0
    ans = -1
    for i in range(4):
        q.put([0, x1, y1, i])
    while not q.empty():
        cost, x, y, vec = q.get()
        if cost > row[x][y]:
            continue
        if x == x2 and y == y2:
            ans = cost
            break
        for i in range(1, k+1):
            nx, ny = x, y
            if vec == 0:
                nx -= i
            elif vec == 1:
                ny += i
            elif vec == 2:
                nx += i
            else:
                ny -= i
            if pond[nx][ny] == 1 or row[nx][ny] < cost + 1:
                break
            row[nx][ny] = cost + 1
            if i < k:
                for j in range(4):
                    if j != vec:
                        row[nx][ny] = cost+1
                        q.put([cost+1, nx, ny, j])
            else:
                for j in range(4):
                    row[nx][ny] = cost+1
                    q.put([cost+1, nx, ny, j])
    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 queue
import sys
input = sys.stdin.readline

def update(x, y, k, cost, pt, vec, pond, row, q, fs):
    for i in range(1, k+1):
        nx, ny = x, y
        nc = cost+1
        if vec == 0:
            nx -= i
        elif vec == 1:
            ny += i
        elif vec == 2:
            nx += i
        else:
            ny -= i
        if pond[nx][ny] == 1:
            return
        if row[nx][ny][vec] > nc:
            row[nx][ny][vec] = nc
            if i == k:
                q.put([nc, nx, ny, i, vec])
            if fs[nx][ny]:
                for j in range(1, 4):
                    if row[nx][ny][(vec+j)%4] > nc:
                        row[nx][ny][(vec+j)%4] = nc
                        q.put([nc, nx, ny, k, (vec+j)%4])
                fs[nx][ny] = False
        else:
            return

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
    q = queue.Queue()
    row = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    fs = [[True]*(w+2) for _ in range(h+2)]
    for i in range(4):
        row[x1][y1][i] = 0
        q.put([0, x1, y1, k, i])
    while not q.empty():
        cost, x, y, pt, vec = q.get()
        if cost > row[x][y][vec]:
            continue
        update(x, y, k, cost, pt, vec, pond, row, q, fs)
    ans = min(row[x2][y2])
    if ans == float("inf"):
        print(-1)
    else:
        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 = []
    row = [[float("inf")]*(w+2) for _ in range(h+2)]
    row[x1][y1] = 0
    ans = -1
    for i in range(4):
        heapq.heappush(hq, [0, x1, y1, i])
    while len(hq) > 0:
        cost, x, y, vec = heapq.heappop(hq)
        if cost > row[x][y]:
            continue
        if x == x2 and y == y2:
            ans = cost
            break
        for i in range(1, k+1):
            nx, ny = x, y
            if vec == 0:
                nx -= i
            elif vec == 1:
                ny += i
            elif vec == 2:
                nx += i
            else:
                ny -= i
            if pond[nx][ny] == 1 or row[nx][ny] < cost + 1:
                break
            row[nx][ny] = cost + 1
            if i < k:
                for j in range(4):
                    if j != vec:
                        row[nx][ny] = cost+1
                        heapq.heappush(hq, [cost+1, nx, ny, j])
            else:
                for j in range(4):
                    row[nx][ny] = cost+1
                    heapq.heappush(hq, [cost+1, nx, ny, j])
    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
import sys
input = sys.stdin.readline

def update(x, y, k, cost, pt, vec, pond, row, hq, fs):
    hpush = heapq.heappush
    for i in range(1, k+1):
        nx, ny = x, y
        nc = cost+1
        if vec == 0:
            nx -= i
        elif vec == 1:
            ny += i
        elif vec == 2:
            nx += i
        else:
            ny -= i
        if pond[nx][ny] == 1:
            return
        if row[nx][ny][vec] > nc:
            row[nx][ny][vec] = nc
            if i == k:
                hpush(hq, [nc, nx, ny, i, vec])
            if fs[nx][ny]:
                for j in range(1, 4):
                    if row[nx][ny][(vec+j)%4] > nc:
                        row[nx][ny][(vec+j)%4] = nc
                        hpush(hq, [nc, nx, ny, k, (vec+j)%4])
                fs[nx][ny] = False
        else:
            return

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 = []
    row = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    fs = [[True]*(w+2) for _ in range(h+2)]
    hpop = heapq.heappop
    for i in range(4):
        row[x1][y1][i] = 0
        heapq.heappush(hq, [0, x1, y1, k, i])
    while len(hq) > 0:
        cost, x, y, pt, vec = hpop(hq)
        if cost > row[x][y][vec]:
            continue
        update(x, y, k, cost, pt, vec, pond, row, hq, fs)
    ans = min(row[x2][y2])
    if ans == float("inf"):
        print(-1)
    else:
        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
import sys
input = sys.stdin.readline

def update(x, y, k, cost, pt, vec, pond, row, hq, fs):
    for i in range(1, k+1):
        nx, ny = x, y
        nc = cost+1
        if vec == 0:
            nx -= i
        elif vec == 1:
            ny += i
        elif vec == 2:
            nx += i
        else:
            ny -= i
        if pond[nx][ny] == 1:
            return
        if row[nx][ny][vec] > nc:
            row[nx][ny][vec] = nc
            if i == k:
                heapq.heappush(hq, [nc, nx, ny, i, vec])
            if fs[nx][ny]:
                for j in range(1, 4):
                    if row[nx][ny][(vec+j)%4] > nc:
                        row[nx][ny][(vec+j)%4] = nc
                        heapq.heappush(hq, [nc, nx, ny, k, (vec+j)%4])
                fs[nx][ny] = False
        else:
            return

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 = []
    row = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    fs = [[True]*(w+2) for _ in range(h+2)]
    for i in range(4):
        row[x1][y1][i] = 0
        heapq.heappush(hq, [0, x1, y1, k, i])
    st = set()
    while len(hq) > 0:
        cost, x, y, pt, vec = heapq.heappop(hq)
        if (x, y, vec) in st:
            continue
        else:
            st.add((x, y, vec))
        update(x, y, k, cost, pt, vec, pond, row, hq, fs)
    ans = min(row[x2][y2])
    if ans == float("inf"):
        print(-1)
    else:
        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
import sys
input = sys.stdin.readline

def update(x, y, k, cost, pt, vec, pond, row, hq, fs):
    for i in range(1, k+1):
        nx, ny = x, y
        nc = cost+1
        if vec == 0:
            nx -= i
        elif vec == 1:
            ny += i
        elif vec == 2:
            nx += i
        else:
            ny -= i
        if pond[nx][ny] == 1:
            return
        if row[nx][ny][vec] > nc:
            row[nx][ny][vec] = nc
            if i == k:
                heapq.heappush(hq, [nc, nx, ny, i, vec])
            if fs[nx][ny]:
                for j in range(1, 4):
                    if row[nx][ny][(vec+j)%4] > nc:
                        row[nx][ny][(vec+j)%4] = nc
                        heapq.heappush(hq, [nc, nx, ny, k, (vec+j)%4])
                fs[nx][ny] = False
        else:
            return

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 = []
    row = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    fs = [[True]*(w+2) for _ in range(h+2)]
    for i in range(4):
        row[x1][y1][i] = 0
        heapq.heappush(hq, [0, x1, y1, k, i])
    while len(hq) > 0:
        cost, x, y, pt, vec = heapq.heappop(hq)
        if cost > row[x][y][vec]:
            continue
        update(x, y, k, cost, pt, vec, pond, row, hq, fs)
    ans = min(row[x2][y2])
    if ans == float("inf"):
        print(-1)
    else:
        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
import sys
input = sys.stdin.readline

def update(x, y, k, cost, pt, vec, pond, row, hq, fs):
    for i in range(1, k+1):
        nx, ny = x, y
        nc = cost+1
        if vec == 0:
            nx -= i
        elif vec == 1:
            ny += i
        elif vec == 2:
            nx += i
        else:
            ny -= i
        if pond[nx][ny] == 1:
            return
        if row[nx][ny][vec] > nc:
            row[nx][ny][vec] = nc
            if i == k:
                heapq.heappush(hq, [nc, nx, ny, i, vec])
            if fs[nx][ny]:
                for j in range(1, 4):
                    if row[nx][ny][(vec+j)%4] > nc:
                        row[nx][ny][(vec+j)%4] = nc
                        heapq.heappush(hq, [nc, nx, ny, k, (vec+j)%4])
                fs[nx][ny] = False
        else:
            return

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 = []
    row = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    fs = [[True]*(w+2) for _ in range(h+2)]
    for i in range(4):
        row[x1][y1][i] = 0
        heapq.heappush(hq, [0, x1, y1, k, i])
    while len(hq) > 0:
        cost, x, y, pt, vec = heapq.heappop(hq)
        if cost > row[x][y][vec]:
            continue
        if pt == k:
            update(x, y, k, cost, pt, vec, pond, row, hq, fs)
    ans = min(row[x2][y2])
    if ans == float("inf"):
        print(-1)
    else:
        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
import sys
input = sys.stdin.readline

def update(x, y, k, cost, pt, vec, pond, row, hq, fs):
    for i in range(1, k+1):
        nx, ny = x, y
        nc = cost+1
        if vec == 0:
            nx -= i
        elif vec == 1:
            ny += i
        elif vec == 2:
            nx += i
        else:
            ny -= i
        if pond[nx][ny] == 1:
            return
        if row[nx][ny][vec] > nc:
            row[nx][ny][vec] = nc
            heapq.heappush(hq, [nc, nx, ny, i, vec])
            if fs[nx][ny]:
                for j in range(1, 4):
                    if row[nx][ny][(vec+j)%4] > nc:
                        row[nx][ny][(vec+j)%4] = nc
                        heapq.heappush(hq, [nc, nx, ny, k, (vec+j)%4])
                fs[nx][ny] = False
        else:
            return

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 = []
    row = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    fs = [[True]*(w+2) for _ in range(h+2)]
    for i in range(4):
        row[x1][y1][i] = 0
        heapq.heappush(hq, [0, x1, y1, k, i])
    while len(hq) > 0:
        cost, x, y, pt, vec = heapq.heappop(hq)
        if cost > row[x][y][vec]:
            continue
        if pt == k:
            update(x, y, k, cost, pt, vec, pond, row, hq, fs)
    ans = min(row[x2][y2])
    if ans == float("inf"):
        print(-1)
    else:
        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
import sys
input = sys.stdin.readline

def update(x, y, k, cost, pt, vec, pond, row, hq):
    for i in range(1, k+1):
        nx, ny = x, y
        nc = cost+1
        if vec == 0:
            nx -= i
        elif vec == 1:
            ny += i
        elif vec == 2:
            nx += i
        else:
            ny -= i
        if pond[nx][ny] == 1:
            return
        if row[nx][ny][vec] > nc:
            row[nx][ny][vec] = nc
            heapq.heappush(hq, [nc, nx, ny, i, vec])
            for j in range(1, 4):
                if row[nx][ny][(vec+j)%4] > nc:
                    row[nx][ny][(vec+j)%4] = nc
                    heapq.heappush(hq, [nc, nx, ny, k, (vec+j)%4])
        else:
            return

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 = []
    row = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    for i in range(4):
        row[x1][y1][i] = 0
        heapq.heappush(hq, [0, x1, y1, k, i])
    while len(hq) > 0:
        cost, x, y, pt, vec = heapq.heappop(hq)
        if cost > row[x][y][vec]:
            continue
        if pt == k:
            update(x, y, k, cost, pt, vec, pond, row, hq)
    ans = min(row[x2][y2])
    if ans == float("inf"):
        print(-1)
    else:
        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 update(x, y, k, cost, pt, vec, pond, row, hq):
    for i in range(1, k+1):
        nx, ny = x, y
        nc = cost+1
        if vec == 0:
            nx -= i
        elif vec == 1:
            ny += i
        elif vec == 2:
            nx += i
        else:
            ny -= i
        if pond[nx][ny] == 1:
            return
        if row[nx][ny][vec] > nc:
            row[nx][ny][vec] = nc
            heapq.heappush(hq, [nc, nx, ny, i, vec])
            for j in range(1, 4):
                if row[nx][ny][(vec+j)%4] > nc:
                    row[nx][ny][(vec+j)%4] = nc
                    heapq.heappush(hq, [nc, nx, ny, k, (vec+j)%4])
        else:
            return

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 = []
    row = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    for i in range(4):
        row[x1][y1][i] = 0
        heapq.heappush(hq, [0, x1, y1, k, i])
    while len(hq) > 0:
        cost, x, y, pt, vec = heapq.heappop(hq)
        if cost > row[x][y][vec]:
            continue
        if pt == k:
            update(x, y, k, cost, pt, vec, pond, row, hq)
    ans = min(row[x2][y2])
    if ans == float("inf"):
        print(-1)
    else:
        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 update(x, y, k, cost, pt, vec, pond, row, hq):
    for i in range(1, k+1):
        nx, ny = x, y
        nc = cost+1
        if vec == 0:
            nx -= i
        elif vec == 1:
            ny += i
        elif vec == 2:
            nx += i
        else:
            ny -= i
        if pond[nx][ny] == 1:
            return
        if row[nx][ny][vec] > nc:
            row[nx][ny][vec] = nc
            heapq.heappush(hq, [nc, nx, ny, i, vec])
            for j in range(1, 4):
                if row[nx][ny][(vec+j)%4] > nc:
                    row[nx][ny][(vec+j)%4] = nc
                    heapq.heappush(hq, [nc, nx, ny, k, (vec+j)%4])

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 = []
    row = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    for i in range(4):
        row[x1][y1][i] = 0
        heapq.heappush(hq, [0, x1, y1, k, i])
    while len(hq) > 0:
        cost, x, y, pt, vec = heapq.heappop(hq)
        if cost > row[x][y][vec]:
            continue
        if pt == k:
            update(x, y, k, cost, pt, vec, pond, row, hq)
    ans = min(row[x2][y2])
    if ans == float("inf"):
        print(-1)
    else:
        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
from numba import jit

@jit
def update(x, y, k, cost, pt, vec, pond, row, hq):
    for i in range(1, k+1):
        nx, ny = x, y
        nc = cost+1
        if vec == 0:
            nx -= i
        elif vec == 1:
            ny += i
        elif vec == 2:
            nx += i
        else:
            ny -= i
        if pond[nx][ny] == 1:
            return
        if row[nx][ny][vec] > nc:
            row[nx][ny][vec] = nc
            heapq.heappush(hq, [nc, nx, ny, i, vec])
            for j in range(1, 4):
                if row[nx][ny][(vec+j)%4] > nc:
                    row[nx][ny][(vec+j)%4] = nc
                    heapq.heappush(hq, [nc, nx, ny, k, (vec+j)%4])

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 = []
    row = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    for i in range(4):
        row[x1][y1][i] = 0
        heapq.heappush(hq, [0, x1, y1, k, i])
    while len(hq) > 0:
        cost, x, y, pt, vec = heapq.heappop(hq)
        if cost > row[x][y][vec]:
            continue
        if pt == k:
            update(x, y, k, cost, pt, vec, pond, row, hq)
    ans = min(row[x2][y2])
    if ans == float("inf"):
        print(-1)
    else:
        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 = []
    row = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    for i in range(4):
        row[x1][y1][i] = 0
        heapq.heappush(hq, [0, x1, y1, k, i])
    while len(hq) > 0:
        cost, x, y, pt, vec = heapq.heappop(hq)
        if cost > row[x][y][vec]:
            continue
        if pt == k:
            i = 1
            while True:
                nx, ny = x, y
                nc = cost+((i+k-1)//k)
                if vec == 0:
                    nx -= i
                elif vec == 1:
                    ny += i
                elif vec == 2:
                    nx += i
                else:
                    ny -= i
                if pond[nx][ny] == 1:
                    break
                if row[nx][ny][vec] > nc:
                    row[nx][ny][vec] = nc
                    heapq.heappush(hq, [nc, nx, ny, i, vec])
                    for j in range(1, 4):
                        if row[nx][ny][(vec+j)%4] > nc:
                            row[nx][ny][(vec+j)%4] = nc
                            heapq.heappush(hq, [nc, nx, ny, k, (vec+j)%4])
                i += 1
    ans = min(row[x2][y2])
    if ans == float("inf"):
        print(-1)
    else:
        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 = []
    row = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    for i in range(4):
        row[x1][y1][i] = 0
        heapq.heappush(hq, [0, x1, y1, k, i])
    while len(hq) > 0:
        cost, x, y, pt, vec = heapq.heappop(hq)
        if cost > row[x][y][vec]:
            continue
        if pt == k:
            for i in range(1, k+1):
                nx, ny = x, y
                nc = cost+1
                if vec == 0:
                    nx -= i
                elif vec == 1:
                    ny += i
                elif vec == 2:
                    nx += i
                else:
                    ny -= i
                if pond[nx][ny] == 1:
                    break
                if row[nx][ny][vec] > nc:
                    row[nx][ny][vec] = nc
                    heapq.heappush(hq, [nc, nx, ny, i, vec])
                    for j in range(1, 4):
                        if row[nx][ny][(vec+j)%4] > nc:
                            row[nx][ny][(vec+j)%4] = nc
                            heapq.heappush(hq, [nc, nx, ny, k, (vec+j)%4])
    ans = min(row[x2][y2])
    if ans == float("inf"):
        print(-1)
    else:
        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 = []
    row = [[[float("inf")]*4 for j in range(w+2)] for i in range(h+2)]
    for i in range(4):
        row[x1][y1][i] = 1
        heapq.heappush(hq, [1, x1, y1, 0, i])
    while len(hq) > 0:
        cost, x, y, pt, vec = heapq.heappop(hq)
        if cost > row[x][y][vec]:
            continue
        if pt == 0 or pt == k:
            for i in range(1, k+1):
                nx, ny = x, y
                nc = cost
                if pt == k:
                    nc += 1
                if vec == 0:
                    nx -= i
                elif vec == 1:
                    ny += i
                elif vec == 2:
                    nx += i
                else:
                    ny -= i
                if pond[nx][ny] == 1:
                    break
                if row[nx][ny][vec] > nc:
                    row[nx][ny][vec] = nc
                    heapq.heappush(hq, [nc, nx, ny, i, vec])
        for i in range(1, 4):
            if row[x][y][(vec+i)%4] > cost+1:
                row[x][y][(vec+i)%4] = cost+1
                heapq.heappush(hq, [cost+1, x, y, 0, (vec+i)%4])
    ans = min(row[x2][y2])
    if ans == float("inf"):
        print(-1)
    else:
        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) for _ in range(h)]
    for i in range(h):
        s = input()
        for j in range(w):
            if s[j] == ".":
                pond[i][j] = 0
    x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1
    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 x-i < 0:
                break
            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 h <= x+i:
                break
            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 y-i < 0:
                break
            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 w <= y+i:
                break
            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) for _ in range(h)]
    for i in range(h):
        s = input()
        for j in range(w):
            if s[j] == ".":
                pond[i][j] = 0
    x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1
    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 x-i < 0:
                break
            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 h <= x+i:
                break
            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 y-i < 0:
                break
            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 w <= y+i:
                break
            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
from numba import jit

@jit
def main(h, w, k, x1, y1, x2, y2, pond):
    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__":
    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
    main(h, w, k, x1, y1, x2, y2, pond)


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
from numba import jit

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

@jit
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)
    brk = 0
    while len(hq) > 0:
        cost, row, pt, x, y, vec = heapq.heappop(hq)
        if cost > ans[x][y][vec]:
            continue
        if x == x2 and y == y2:
            brk += 1
        if brk == 4:
            break
        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()