Problem p02644 (python)

Fixed submission:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
def LI(): return [int(x) for x in sys.stdin.readline().split()]

dd = [(1,0),(-1,0),(0,1),(0,-1)]

def solve():
    h,w,k = LI()
    y,x,s,t = LI()
    y -= 1
    x -= 1
    s -= 1
    t -= 1
    c = [input() for i in range(h)]
    q = deque([(y,x)])
    d = [[float("inf")]*w for i in range(h)]
    d[y][x] = 0
    while q:
      y,x = q.popleft()
      if (y,x) == (s,t):
          print(d[s][t])
          return
      nd = d[y][x] + 1
      for dy,dx in dd:
          ny,nx = y,x
          for _ in range(k):
              ny += dy
              nx += dx
              if 0 <= ny < h and 0 <= nx < w and c[ny][nx] != "@" and nd <= d[ny][nx]:
                  if nd < d[ny][nx]:
                      d[ny][nx] = nd
                      q.append((ny,nx))
                  continue
              break
    print(-1)
    return

#Solve
if __name__ == "__main__":
    solve()

Buggy submission (verdict: Runtime Error):
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

dd = [(1,0),(-1,0),(0,1),(0,-1)]
def solve():
    h,w,k = LI()
    y,x,s,t = LI()
    y -= 1
    x -= 1
    s -= 1
    t -= 1
    c = [input() for i in range(h)]
    q = deque([(y,x,-1)])
    d = [[float("inf")]*w for i in range(h)]
    d[y][x] = 0
    ri = [[0]*w for i in range(h)]
    le = [[0]*w for i in range(h)]
    do = [[0]*w for i in range(h)]
    up = [[0]*w for i in range(h)]

    for i in range(h):
        ri[i][-1] = 0
        for j in range(w-1)[::-1]:
            if c[i][j+1] == "@":
                ri[i][j] = 0
            else:
                l = ri[i][j+1]
                if l < k:
                    ri[i][j] = l+1
                else:
                    ri[i][j] = k
    for i in range(h):
        le[i][0] = 0
        for j in range(1,w):
            if c[i][j-1] == "@":
                le[i][j] = 0
            else:
                l = le[i][j-1]
                if l < k:
                    le[i][j] = l+1
                else:
                    le[i][j] = k

    for j in range(w):
        do[-1][j] = 0
        for i in range(h-1)[::-1]:
            if c[i+1][j] == "@":
                do[i][j] = 0
            else:
                l = do[i+1][j]
                if l < k:
                    do[i][j] = l+1
                else:
                    do[i][j] = k
    for j in range(w):
        up[0][j] = 0
        for i in range(1,h):
            if c[i-1][j] == "@":
                up[i][j] = 0
            else:
                l = up[i-1][j]
                if l < k:
                    up[i][j] = l+1
                else:
                    up[i][j] = k
    while q:
        y,x,p = q.popleft()
        nd = d[y][x] + 1
        for i in range(4):
            if i == 0:
                dy,dx = -up[y][x],0
            elif i == 1:
                dy,dx = do[y][x],0
            elif i == 2:
                dy,dx = 0,-le[y][x]
            else:
                dy,dx = 0,ri[y][x]
            ny,nx = y+dy,x+dx
            if (y,x) == (ny,nx):
                continue
            if nd < d[ny][nx]:
                d[ny][nx] = nd
                q.append((ny,nx,i))
        if p >= 0:
            dy,dx = dd[p]
            ny,nx = y+dy,x+dx
            nd = d[y][x]
            if nd < d[ny][nx]:
                d[ny][nx] = nd
                q.appendleft((ny,nx,p))
    ans = d[s][t]
    if ans < float("inf"):
        print(ans)
    else:
        print(-1)
    return

#Solve
if __name__ == "__main__":
    solve()