Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush 
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()

    # 多分正解だけどpythonではTLEする。
    def dijkstra():
        def toId(x, y, v): return (x*w+y)*4 + v

        def modCeil(x): return x + (-x)%k

        def push(x, y, v, cost):
            nId = toId(x, y, v)
            if dist[nId] > cost:
                dist[nId] = cost
                heappush(que, (cost, nId))

        inf = 1e18

        dist = [inf]*(h*w*4)
        dist[toId(xs, ys, 0)] = 0

        que = [(0, toId(xs, ys, 0))]
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while que:
            cost, Id = heappop(que)
            x = Id//4//w
            y = Id//4%w
            v = Id%4

            if cost > dist[Id]:
                continue
            
            for nv in range(4):
                nx = x + dx[nv]
                ny = y + dy[nv]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: continue
                if field[nx][ny] == '@': continue
                if v == nv:
                    push(nx, ny, nv, cost+1)
                else:
                    push(nx, ny, nv, modCeil(cost)+ 1)
            
        ans = min([dist[toId(xg, yg, v)] for v in range(4)])
        if ans == inf:
            print(-1)
        else:
            print(modCeil(ans)//k)
        

    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]
    dijkstra()


if __name__ == '__main__':
    main()

Fixed submission:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush 
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()

    # 多分正解だけどpythonではTLEする。
    def dijkstra():
        def toId(x, y, v): return (x*w+y)*4 + v

        def modCeil(x): return x + (-x)%k

        def push(x, y, v, cost):
            nId = toId(x, y, v)
            if dp[nId] > cost:
                dp[nId] = cost
                heappush(que, (cost, nId))

        inf = 1e18

        dp = [inf]*(h*w*4)
        dp[toId(xs, ys, 0)] = 0

        que = [(0, toId(xs, ys, 0))]
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while que:
            cost, Id = heappop(que)
            x = Id//4//w
            y = Id//4%w
            v = Id%4

            if cost > dp[Id]:
                continue
            
            for nv in range(4):
                push(x, y, nv, modCeil(cost))
            
            nx, ny = x+dx[v], y+dy[v]
            if 0 <= nx < h and 0 <= ny < w and field[nx][ny] == '.':
                push(nx, ny, v, cost+1)

        ans = inf
        for v in range(4):
            ans = min(ans, dp[toId(xg, yg, v)])
        if ans == inf:     
            return print(-1)
        return print(modCeil(ans)//k)

    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]
    dijkstra()


if __name__ == '__main__':
    main()

Fixed submission:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    from collections import deque
    def input(): return sys.stdin.readline().rstrip()
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if 0 <= nx < h and 0 <= ny < w:
                    if field[nx][ny] == '@': break
                    if dist[nx][ny] <= dist[x][y]: break
                    if dist[nx][ny] > dist[x][y] + 1:
                        dist[nx][ny] = dist[x][y] + 1
                        que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()

Fixed submission:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    from collections import deque
    def input(): return sys.stdin.readline().rstrip()

    def bfs():
        inf = 1e7

        dist = [[inf]*w for _ in range(h)]
        dist[xs][ys] = 0
        que = deque([(xs, ys)])
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while que:
            x, y = que.popleft()
            for i in range(4):
                nx, ny = x, y
                for _ in range(k):
                    nx += dx[i]
                    ny += dy[i]
                    if 0 <= nx < h and 0 <= ny < w:
                        if field[nx][ny] == '@': break
                        if dist[nx][ny] <= dist[x][y]: break
                        if dist[nx][ny] > dist[x][y] + 1:
                            dist[nx][ny] = dist[x][y] + 1
                            que.append((nx, ny))
        
        if dist[xg][yg] == inf:
            print(-1)
        else:
            print(dist[xg][yg])


               

    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]
    bfs()


if __name__ == '__main__':
    main()

Fixed submission:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    from collections import deque
    def input(): return sys.stdin.readline().rstrip()

    def bfs():
        inf = 1e18

        dist = [[inf]*w for _ in range(h)]
        dist[xs][ys] = 0
        que = deque([(xs, ys)])
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while que:
            x, y = que.popleft()

            if (x,y) == (xg, yg):
                return dist[x][y]

            for i in range(4):
                nx, ny = x, y
                for _ in range(k):
                    nx += dx[i]
                    ny += dy[i]
                    if 0 <= nx < h and 0 <= ny < w:
                        if field[nx][ny] == '@': break
                        if dist[nx][ny] <= dist[x][y]: break
                        if dist[nx][ny] > dist[x][y] + 1:
                            dist[nx][ny] = dist[x][y] + 1
                            que.append((nx, ny))
        if dist[xg][yg] == inf:
            return -1


               

    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]
    ans = bfs()
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush 
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()

    
    def dijkstra():
        def toId(x, y, v): return (x*w+y)*4 + v

        def modCeil(x): return x + (-x)%k

        def push(x, y, v, cost):
            nId = toId(x, y, v)
            if dp[nId] > cost:
                dp[nId] = cost
                heappush(que, (cost, nId))

        inf = 1e18

        dp = [inf]*(h*w*4)
        dp[toId(xs, ys, 0)] = 0

        que = [(0, toId(xs, ys, 0))]
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while que:
            cost, Id = heappop(que)
            x = Id//4//w
            y = Id//4%w
            v = Id%4

            if cost > dp[Id]:
                continue
            
            if x == xg and y == yg:
                return modCeil(cost)//k
            
            for nv in range(4):
                push(x, y, nv, modCeil(cost))
            
            nx, ny = x+dx[v], y+dy[v]
            if 0 <= nx < h and 0 <= ny < w and field[nx][ny] == '.':
                push(nx, ny, v, cost+1)

        ans = inf
        for v in range(4):
            ans = min(ans, dp[toId(xg, yg, v)])
        if ans == inf:     
            return -1
        return modCeil(ans)//k

    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]
    ans = dijkstra()
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush 
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()

    
    def dijkstra():
        def toId(x, y, v): return (x*w+y)*4 + v

        def modCeil(x): return x + (-x)%k

        def push(x, y, v, cost):
            nId = toId(x, y, v)
            if dp[nId] > cost:
                dp[nId] = cost
                heappush(que, (cost, nId))

        inf = 1e18

        dp = [inf]*(h*w*4)
        dp[toId(xs, ys, 0)] = 0

        que = [(0, toId(xs, ys, 0))]
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while que:
            cost, Id = heappop(que)
            x = Id//4//w
            y = Id//4%w
            v = Id%4

            if cost > dp[Id]:
                continue
            
            for nv in range(4):
                push(x, y, nv, modCeil(cost))
            
            nx, ny = x+dx[v], y+dy[v]
            if 0 <= nx < h and 0 <= ny < w:
                if field[nx][ny] == '.':
                    push(nx, ny, v, cost+1)

        ans = inf
        for v in range(4):
            ans = min(ans, dp[toId(xg, yg, v)])
        if ans == inf:     
            return -1
        return modCeil(ans)//k

    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = []
    for _ in range(h):
        field.append(input())
    
    ans = dijkstra()
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush 
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()

    
    def dijkstra():
        def toId(x, y, v): return (x*(w+2)+y)*4 + v

        def modCeil(x): return x + (-x)%k

        def push(x, y, v, cost):
            nId = toId(x, y, v)
            if dp[nId] > cost:
                dp[nId] = cost
                heappush(que, (cost, nId))

        inf = 1e18

        dp = [inf]*(h+2)*(w+2)*4
        dp[toId(xs, ys, 0)] = 0

        que = [(0, toId(xs, ys, 0))]
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while que:
            cost, Id = heappop(que)
            x = Id//4//(w+2)
            y = Id//4%(w+2)
            v = Id%4

            if cost > dp[Id]:
                continue
            
            for nv in range(4):
                push(x, y, nv, modCeil(cost))
            
            nx, ny = x+dx[v], y+dy[v]
            if field[nx][ny] == '.':
                push(nx, ny, v, cost+1)

        ans = inf
        for v in range(4):
            ans = min(ans, dp[toId(xg, yg, v)])
        if ans == inf:     
            return -1
        return modCeil(ans)//k

    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(int, input().split())
    field = ['@'*(w+2)]
    for _ in range(h):
        field.append('@'+input()+'@')
    field.append('@'*(w+2))
    ans = dijkstra()
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush 
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()

    
    def dijkstra():
        def toId(x, y, v): return (x*(w+2)+y)*4 + v

        def modCeil(x): return x + (-x)%k

        def push(x, y, v, cost):
            nId = toId(x, y, v)
            if dp[nId] > cost:
                dp[nId] = cost
                heappush(que, (cost, nId))

        inf = 1e18

        dp = [inf]*(h+2)*(w+2)*4
        dp[toId(xs, ys, 0)] = 0

        que = [(0, toId(xs, ys, 0))]
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while que:
            cost, Id = heappop(que)
            x = Id//4//(w+2)
            y = Id//4%(w+2)
            v = Id%4

            if cost > dp[Id]:
                continue
            
            for nv in range(4):
                push(x, y, nv, modCeil(cost))
            
            nx, ny = x+dx[v], y+dy[v]
            if field[nx][ny]:
                push(nx, ny, v, cost+1)

        ans = inf
        for v in range(4):
            ans = min(ans, dp[toId(xg, yg, v)])
        if ans == inf:       
            return -1
        return modCeil(ans)//k

    h, w, k= map(int, input().split())
    xs, ys, xg, yg = map(int, input().split())
    field = [[False]*(w+2)]
    for _ in range(h):
        s = [False]
        s += [True if i == '.' else False for i in input()]
        s += [False]
        field.append(s)
    field.append([False]*(w+2))
    ans = dijkstra()
    print(ans)




if __name__ == '__main__':
    main()

Fixed submission:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush 
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()

    def toId(x, y, v): return (x*(w+2)+y)*4 + v

    def modCeil(x): return x + (-x)%k

    def dijkstra():
        inf = 1e18

        dp = [inf]*(h+2)*(w+2)*4
        dp[toId(xs, ys, 0)] = 0

        que = [(0, toId(xs, ys, 0))]
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while que:
            cost, Id = heappop(que)
            x = Id//4//(w+2)
            y = Id//4%(w+2)
            v = Id%4

            if cost > dp[Id]:
                continue
            
            for nv in range(4):
                nId = toId(x, y, nv)
                if dp[nId] > cost:
                    dp[nId] = modCeil(cost)
                    heappush(que, (dp[nId], nId))
            
            nx, ny = x+dx[v], y+dy[v]
            nId = toId(nx, ny, v)
            if field[nx][ny]:
                if dp[nId] > cost + 1:
                    dp[nId] = cost + 1
                    heappush(que, (dp[nId], nId))

        ans = inf
        for v in range(4):
            ans = min(ans, dp[toId(xg, yg, v)])
        if ans == inf:       
            return -1
        return modCeil(ans)//k

    h, w, k= map(int, input().split())
    xs, ys, xg, yg = map(int, input().split())
    field = [[False]*(w+2)]
    for _ in range(h):
        s = [False]
        s += [True if i == '.' else False for i in input()]
        s += [False]
        field.append(s)
    field.append([False]*(w+2))
    ans = dijkstra()
    print(ans)




if __name__ == '__main__':
    main()

Fixed submission:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush 
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    def dijkstra():
        inf = 10 ** 18

        dp = [[[inf]*4 for _ in range(w+2)] for _ in range(h+2)]
        dp[xs][ys][0] = 0

        que = [(0, xs, ys, 0)]
        direction = [[-1, 0], [0, 1], [1, 0], [0, -1]]
        while que:
            cost, x, y, dirt = heappop(que)

            if cost > dp[x][y][dirt]:
                continue

            if (x, y) == (xg, yg):
                ans = (dp[x][y][dirt] + (-dp[x][y][dirt]) % k)//k
                return ans

            for i in range(4):
                nx, ny = x + direction[i][0], y + direction[i][1]
                if field[nx][ny]:
                    if i == dirt:
                        if dp[nx][ny][i] > dp[x][y][i] + 1:
                            dp[nx][ny][i] = dp[x][y][i] + 1
                            heappush(que, (dp[nx][ny][i], nx, ny, i))
                    else:
                        if dp[x][y][i] > dp[x][y][dirt] + (-dp[x][y][dirt])%k:
                            dp[x][y][i] = dp[x][y][dirt] + (-dp[x][y][dirt])%k
                            heappush(que, (dp[x][y][i], x, y, i))
        return -1


    h, w, k= map(int, input().split())
    xs, ys, xg, yg = map(int, input().split())
    field = [[False]*(w+2)]
    for _ in range(h):
        s = [False]
        s += [True if i == '.' else False for i in input()]
        s += [False]
        field.append(s)
    field.append([False]*(w+2))
    ans = dijkstra()
    print(ans)




if __name__ == '__main__':
    main()

Fixed submission:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
from heapq import heappop, heappush 
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    def dijkstra():
        inf = 10 ** 9
        visited = [[False]*(w+2) for _ in range(h+2)]

        dp = [[inf]*(w+2) for _ in range(h+2)]
        dp[xs][ys] = 0

        que = [(0, xs, ys, 0)]
        direction = [[-1, 0], [0, 1], [1, 0], [0, -1]]
        while que:
            cost, x, y, dirt = heappop(que)
            # if (x, y) == (xg, yg):
            #     ans = (dp[x][y] + k - 1)//k
            #     return ans

            if not visited[x][y]:
                for i in range(4):
                    nx, ny = x + direction[i][0], y + direction[i][1]
                    if field[nx][ny]:
                        if i == dirt:
                            if dp[nx][ny] > dp[x][y] + 1:
                                dp[nx][ny] = dp[x][y] + 1
                                heappush(que, (dp[nx][ny], nx, ny, i))
                        else:
                            if dp[nx][ny] > (dp[x][y] + k-1)//k*k + 1:
                                dp[nx][ny] = (dp[x][y] + k-1)//k*k + 1
                                heappush(que, (dp[nx][ny], nx, ny, i))
                visited[x][y] = True
        if dp[xg][yg] == inf
            return -1
        else:
            return (dp[xg][yg] + k - 1)//k


    h, w, k= map(int, input().split())
    xs, ys, xg, yg = map(int, input().split())
    field = [[False]*(w+2)]
    for _ in range(h):
        s = [False]
        s += [True if i == '.' else False for i in input()]
        s += [False]
        field.append(s)
    field.append([False]*(w+2))
    ans = dijkstra()
    print(ans)




if __name__ == '__main__':
    main()

Fixed submission:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush 
def dijkstra(xs, ys, xg, yg,h,w,k,field):
    # que->(cost, x, y)
    que = [(0, xs, ys)]
    inf = 10 ** 6
    dp = [[inf for _ in range(w+1)] for _ in range(h+1)]
    visited = [[False for _ in range(w+1)] for _ in range(h+1)]
    dp[xs][ys] = 0
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]
    while que:
        cost, x, y= heappop(que)
        # 現在のコストより高いなら無視する
        # if cost > dp[x][y]:
        #     continue
        if x == xg and y == yg:
            print(cost)
            exit(0)
        if not visited[x][y]:
            for i in range(4):
                for j in range(1, k+1):
                    x_, y_ = x+j*dx[i], y+j*dy[i]
                    if not field[x_][y_]:
                        break
                    if dp[x_][y_] > dp[x][y] + 1:
                        dp[x_][y_] = dp[x][y] + 1
                        heappush(que, (dp[x_][y_], x_, y_))
        visited[x][y] = True
    print(-1)
        

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(int, input().split())
    field = [[False]*(w+2) for _ in range(h+2)]
    for i in range(h):
        # False で覆うことでx,yの制限をなくす。
        s = [True if _ == '.' else False for _ in input()]
        field[i+1] = [False]+s+[False]
    dijkstra(xs, ys, xg, yg, h, w, k, field)

if __name__ == '__main__':
    main()

Fixed submission:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
from heapq import heappop, heappush 
def dijkstra(xs, ys, xg, yg,h,w,k,field):
    # que->(cost, x, y)
    que = [(0, xs, ys)]
    inf = 10 ** 6
    dp = [[inf for _ in range(w+1)] for _ in range(h+1)]
    visited = [[False for _ in range(w+1)] for _ in range(h+1)]
    dp[xs][ys] = 0
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]
    while que:
        cost, x, y= heappop(que)
        # 現在のコストより高いなら無視する
        # if cost > dp[x][y]:
        #     continue
        if x == xg and y == yg:
            print(cost)
            exit(0)
        if visited[x][y]
            for i in range(4):
                for j in range(1, k+1):
                    x_, y_ = x+j*dx[i], y+j*dy[i]
                    if not field[x_][y_]:
                        break
                    if dp[x_][y_] > dp[x][y] + 1:
                        dp[x_][y_] = dp[x][y] + 1
                        heappush(que, (dp[x_][y_], x_, y_))
        visited[x][y] = True
    print(-1)
        

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(int, input().split())
    field = [[False]*(w+2) for _ in range(h+2)]
    for i in range(h):
        # False で覆うことでx,yの制限をなくす。
        s = [True if _ == '.' else False for _ in input()]
        field[i+1] = [False]+s+[False]
    dijkstra(xs, ys, xg, yg, h, w, k, field)

if __name__ == '__main__':
    main()

Fixed submission:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush 
def dijkstra(xs, ys, xg, yg,h,w,k,field):
    # que->(cost, x, y)
    que = [(0, xs, ys)]
    inf = 10 ** 6 * k
    dp = [[inf for _ in range(w+1)] for _ in range(h+1)]
    dp[xs][ys] = 0
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]
    while que:
        cost, x, y= heappop(que)
        # 現在のコストより高いなら無視する
        if cost > dp[x][y]:
            continue
        if x == xg and y == yg:
            print(cost)
            exit(0)
        for i in range(4):
            for j in range(1, k+1):
                x_, y_ = x+j*dx[i], y+j*dy[i]
                if not field[x_][y_]:
                    break
                if dp[x_][y_] > dp[x][y] + 1:
                    dp[x_][y_] = dp[x][y] + 1
                    heappush(que, (dp[x_][y_], x_, y_))
    print(-1)
        

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(int, input().split())
    field = [[False]*(w+2) for _ in range(h+2)]
    inf = 10 ** 6 * k
    for i in range(h):
        # False で覆うことでx,yの制限をなくす。
        s = [True if _ == '.' else False for _ in input()]
        field[i+1] = [False]+s+[False]
    dijkstra(xs, ys, xg, yg, h, w, k, field)

if __name__ == '__main__':
    main()

Fixed submission:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
import sys

def main(lines):
    n, m, s = map(int,lines[0].split())
    adj = [[] for _ in range(n)]
    for i in range(m):
        a,b,d = map(int,lines[i+1].split())
        adj[a].append((b,d))
    from heapq import heappush, heappop
    inf = 10**9
    node = []
    dist = [inf]*n
    done = [False]*n
    dist[s] = 0
    heappush(node,(0,s))
    while node:
        cost, v = heappop(node)
        if not done[v]:
            for e in adj[v]:
                if dist[e[0]] > dist[v]+e[1]:
                    dist[e[0]] = dist[v] + e[1]
                    heappush(node, (dist[e[0]],e[0]))
        done[v] = True
    for el in dist:
        if el == inf:
            print('INF') 
        else:
            print(el)       


if __name__ == '__main__':
    lines = []
    for l in sys.stdin:
        lines.append(l.rstrip('\r\n'))
    main(lines)


Fixed submission:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush 
def dijkstra(xs, ys, xg, yg,h,w,k,field):
    # que->(cost, x, y)
    que = [(0, xs, ys)]
    inf = 10 ** 6 * k
    dp = [[inf for _ in range(w+1)] for _ in range(h+1)]
    dp[xs][ys] = 0
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]
    while que:
        cost, x, y= heappop(que)
        # 現在のコストより高いなら無視する
        if cost > dp[x][y]:
            continue
        if x == xg and y == yg:
            return cost
        for i in range(4):
            for j in range(1, k+1):
                x_, y_ = x+j*dx[i], y+j*dy[i]
                if not field[x_][y_]:
                    break
                if dp[x_][y_] > dp[x][y] + 1:
                    dp[x_][y_] = dp[x][y] + 1
                    heappush(que, (dp[x_][y_], x_, y_))
    return dp[xg][yg]
        

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    

    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(int, input().split())
    field = [[False]*(w+2) for _ in range(h+2)]
    inf = 10 ** 6 * k
    for i in range(h):
        #False で覆うことでx,yの制限をなくす。
        s = [True if _ == '.' else False for _ in input()]
        field[i+1] = [False]+s+[False]
    ans = dijkstra(xs,ys,xg,yg,h,w,k,field)
    if ans == inf:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Fixed submission:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()