Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
from collections import deque

def main():
  h, w, k = map(int, input().split())
  x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
  v1 = x1*(w+1)+y1
  v2 = x2*(w+1)+y2
  C = "".join(input().rstrip()+"@" for _ in range(h))
  dist = tuple(-1 if c=="@" else 10**10 for c in C)
  ans = 0
  que = deque()
  que.append(v1)
  dist[v1] = 0
  while que:
    v = que.popleft()
    if v == v2:
      print(dist[v2])
      exit()
    d = dist[v]+1
    for dr in (-(w+1), -1, w+1, 1):
      for i in range(1, k+1):
        nv = v+dr*i
        if 0 <= nv < h*(w+1):
          if dist[nv] > d:
            dist[nv] = d
            que.append(nv)
          elif dist[nv] == d:
            continue
          else:
            break
        else:
          break
  print(-1)
if __name__ == "__main__":
  main()

Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque

def main():
  h, w, k = map(int, input().split())
  x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
  v1 = x1*(w+1)+y1
  v2 = x2*(w+1)+y2
  C = "".join(input().rstrip()+"@" for _ in range(h))
  dist = [-1 if c=="@" else 10**10 for c in C]
  ans = 0
  que = deque()
  que.append(v1)
  dist[v1] = 0
  while que:
    v = que.popleft()
    if v == v2:
      print(dist[v2])
      exit()
    d = dist[v]+1
    for dr in (-(w+1), -1, w+1, 1):
      for i in range(1, k+1):
        nv = v+dr*i
        if 0 <= nv < h*(w+1):
          if dist[nv] > d:
            dist[nv] = d
            que.append(nv)
          elif dist[nv] == d:
            continue
          else:
            break
        else:
          break
  print(-1)
if __name__ == "__main__":
  main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
  h, w, k = map(int, input().split())
  x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
  v1 = x1*(w+1)+y1
  v2 = x2*(w+1)+y2
  C = list("".join(input().rstrip()+"@" for _ in range(h)))
  ans = 0
  stack = [v1]
  next_vs = set()
  while stack:
    for v in stack:
      if v == v2:
        print(ans)
        exit()
      for dr in (-(w+1), -1, 1, w+1):
        for i in range(1, k+1):
          nv = v+dr*i
          if 0 <= nv < h*(w+1) and C[nv] == ".":
            next_vs.add(nv)
          else:
            break
    for v in stack:
      C[v] = "@"
    stack = list(next_vs)
    next_vs = set()
    ans += 1
  else:
    print(-1)
if __name__ == "__main__":
  main()

Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque

def main():
  h, w, k = map(int, input().split())
  x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
  v1 = x1*(w+1)+y1
  v2 = x2*(w+1)+y2
  C = "".join(input().rstrip()+"@" for _ in range(h))
  dist = [-1 if c=="@" else 10**10 for c in C]
  ans = 0
  que = deque()
  que.append(v1)
  dist[v1] = 0
  while que:
    v = que.popleft()
    if v == v2:
      print(dist[v2])
      exit()
    d = dist[v]+1
    for dr in (-(w+1), -1, w+1, 1):
      for i in range(1, k+1):
        nv = v+dr*i
        if 0 <= nv < h*(w+1):
          if dist[nv] > d:
            dist[nv] = d
            que.append(nv)
          elif dist[nv] == d:
            continue
          else:
            break
        else:
          break
  print(-1)
if __name__ == "__main__":
  main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
  h, w, k = map(int, input().split())
  x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
  v1 = x1*(w+1)+y1
  v2 = x2*(w+1)+y2
  C = list("".join(input().rstrip()+"@" for _ in range(h)))
  ans = 0
  stack = [v1]
  next_vs = set()
  while stack:
    for v in stack:
      if v == v2:
        print(ans)
        exit()
      for dr in (-(w+1), -1, 1, w+1):
        for i in range(1, k+1):
          nv = v+dr*i
          if 0 <= nv < h*(w+1) and C[nv] == ".":
            next_vs.add(nv)
          else:
            break
    for v in stack:
      C[v] = "@"
    stack = list(next_vs)
    next_vs = set()
    ans += 1
  else:
    print(-1)
if __name__ == "__main__":
  main()

Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque

def main():
  h, w, k = map(int, input().split())
  x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
  v1 = x1*(w+1)+y1
  v2 = x2*(w+1)+y2
  C = "".join(input().rstrip()+"@" for _ in range(h))
  dist = [-1 if c=="@" else 10**10 for c in C]
  ans = 0
  que = deque()
  que.append(v1)
  dist[v1] = 0
  while que:
    v = que.popleft()
    if v == v2:
      print(dist[v2])
      exit()
    d = dist[v]+1
    for dr in (-(w+1), -1, w+1, 1):
      for i in range(1, k+1):
        nv = v+dr*i
        if 0 <= nv < h*(w+1):
          if dist[nv] > d:
            dist[nv] = d
            que.append(nv)
          elif dist[nv] == d:
            continue
          else:
            break
        else:
          break
  print(-1)
if __name__ == "__main__":
  main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
v1 = x1*(w+1)+y1
v2 = x2*(w+1)+y2
C = list("".join(input().rstrip()+"@" for _ in range(h)))
ans = 0
stack = [v1]
next_vs = set()
while stack:
  for v in stack:
    if v == v2:
      print(ans)
      exit()
    for dr in (-(w+1), -1, 1, w+1):
      for i in range(1, k+1):
        nv = v+dr*i
        if 0 <= nv < h*(w+1) and C[nv] == ".":
          next_vs.add(nv)
        else:
          break
  for v in stack:
    C[v] = "@"
  stack = list(next_vs)
  next_vs = set()
  ans += 1
else:
  print(-1)

Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque

def main():
  h, w, k = map(int, input().split())
  x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
  v1 = x1*(w+1)+y1
  v2 = x2*(w+1)+y2
  C = "".join(input().rstrip()+"@" for _ in range(h))
  dist = [-1 if c=="@" else 10**10 for c in C]
  ans = 0
  que = deque()
  que.append(v1)
  dist[v1] = 0
  while que:
    v = que.popleft()
    if v == v2:
      print(dist[v2])
      exit()
    d = dist[v]+1
    for dr in (-(w+1), -1, w+1, 1):
      for i in range(1, k+1):
        nv = v+dr*i
        if 0 <= nv < h*(w+1):
          if dist[nv] > d:
            dist[nv] = d
            que.append(nv)
          elif dist[nv] == d:
            continue
          else:
            break
        else:
          break
  print(-1)
if __name__ == "__main__":
  main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
import heapq

def main():
  h, w, k = map(int, input().split())
  x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
  S = [input().rstrip() for _ in range(h)]
  dist = [[[float("inf")]*w  for i in range(h)] for _ in range(4)]
  que = []
  que.append((0, 0, x1, y1))
  dist[0][x1][y1] = 0

  while que:
    c, di, x, y = heapq.heappop(que)
    if dist[di][x][y] < c:
      continue
    l, r = c+1, -(-c//k)*k
    if di == 0:
      if x > 0 and S[x-1][y] == "." and dist[di][x-1][y] > l:
        dist[di][x-1][y] = l
        heapq.heappush(que, (l, di, x-1, y))
    elif di == 1:
      if y > 0 and S[x][y-1] == "." and dist[di][x][y-1] > l:
        dist[di][x][y-1] = l
        heapq.heappush(que, (l, di, x, y-1))
    elif di == 2:
      if x < h-1 and S[x+1][y] == "." and dist[di][x+1][y] > l:
        dist[di][x+1][y] = l
        heapq.heappush(que, (l, di, x+1, y))
    else:
      if y < w-1 and S[x][y+1] == "." and dist[di][x][y+1] > l:
        dist[di][x][y+1] = l
        heapq.heappush(que, (l, di, x, y+1))

    if di%2:
      if dist[0][x][y] > r:
        dist[0][x][y] = r
        heapq.heappush(que, (r, 0, x, y))
      if dist[2][x][y] > r:
        dist[2][x][y] = r
        heapq.heappush(que, (r, 2, x, y))

    else:
      if dist[1][x][y] > r:
        dist[1][x][y] = r
        heapq.heappush(que, (r, 1, x, y))
      if dist[3][x][y] > r:
        dist[3][x][y] = r
        heapq.heappush(que, (r, 3, x, y))
  t = min(dist[0][x2][y2], dist[1][x2][y2], dist[2][x2][y2], dist[3][x2][y2])
  if t == float("inf"):
    print(-1)
  else:
    ans = -(-t//k)
    print(ans)

if __name__ == "__main__":
  main()

Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque

def main():
  h, w, k = map(int, input().split())
  x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
  v1 = x1*(w+1)+y1
  v2 = x2*(w+1)+y2
  C = "".join(input().rstrip()+"@" for _ in range(h))
  dist = [-1 if c=="@" else 10**10 for c in C]
  ans = 0
  que = deque()
  que.append(v1)
  dist[v1] = 0
  while que:
    v = que.popleft()
    if v == v2:
      print(dist[v2])
      exit()
    d = dist[v]+1
    for dr in (-(w+1), -1, w+1, 1):
      for i in range(1, k+1):
        nv = v+dr*i
        if 0 <= nv < h*(w+1):
          if dist[nv] > d:
            dist[nv] = d
            que.append(nv)
          elif dist[nv] == d:
            continue
          else:
            break
        else:
          break
  print(-1)
if __name__ == "__main__":
  main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
import heapq

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
S = [input().rstrip() for _ in range(h)]
dist = [[[float("inf")]*w  for i in range(h)] for _ in range(4)]
que = []
que.append((0, 0, x1, y1))
dist[0][x1][y1] = 0
  
while que:
  c, di, x, y = heapq.heappop(que)
  if x == x2 and y == y2:
    break
  if dist[di][x][y] < c:
    continue
  l, r = c+1, -(-c//k)*k
  if di == 0:
    if x > 0 and S[x-1][y] == "." and dist[di][x-1][y] > l:
      dist[di][x-1][y] = l
      heapq.heappush(que, (l, di, x-1, y))
  elif di == 1:
    if y > 0 and S[x][y-1] == "." and dist[di][x][y-1] > l:
      dist[di][x][y-1] = l
      heapq.heappush(que, (l, di, x, y-1))
  elif di == 2:
    if x < h-1 and S[x+1][y] == "." and dist[di][x+1][y] > l:
      dist[di][x+1][y] = l
      heapq.heappush(que, (l, di, x+1, y))
  else:
    if y < w-1 and S[x][y+1] == "." and dist[di][x][y+1] > l:
      dist[di][x][y+1] = l
      heapq.heappush(que, (l, di, x, y+1))
      
  if di%2:
    if dist[0][x][y] > r:
      dist[0][x][y] = r
      heapq.heappush(que, (r, 0, x, y))
    if dist[2][x][y] > r:
      dist[2][x][y] = r
      heapq.heappush(que, (r, 2, x, y))
    
  else:
    if dist[1][x][y] > r:
      dist[1][x][y] = r
      heapq.heappush(que, (r, 1, x, y))
    if dist[3][x][y] > r:
      dist[3][x][y] = r
      heapq.heappush(que, (r, 3, x, y))
t = min(dist[0][x2][y2], dist[1][x2][y2], dist[2][x2][y2], dist[3][x2][y2])
if t == float("inf"):
  print(-1)
else:
  ans = -(-t//k)
  print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque

def main():
  h, w, k = map(int, input().split())
  x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
  v1 = x1*(w+1)+y1
  v2 = x2*(w+1)+y2
  C = "".join(input().rstrip()+"@" for _ in range(h))
  dist = [-1 if c=="@" else 10**10 for c in C]
  ans = 0
  que = deque()
  que.append(v1)
  dist[v1] = 0
  while que:
    v = que.popleft()
    if v == v2:
      print(dist[v2])
      exit()
    d = dist[v]+1
    for dr in (-(w+1), -1, w+1, 1):
      for i in range(1, k+1):
        nv = v+dr*i
        if 0 <= nv < h*(w+1):
          if dist[nv] > d:
            dist[nv] = d
            que.append(nv)
          elif dist[nv] == d:
            continue
          else:
            break
        else:
          break
  print(-1)
if __name__ == "__main__":
  main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
import heapq

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
S = [input().rstrip() for _ in range(h)]
dist = [[[float("inf")]*w  for i in range(h)] for _ in range(4)]
que = []
que.append((0, 0, x1, y1))
dist[0][x1][y1] = 0
  
while que:
  c, di, x, y = heapq.heappop(que)
  if dist[di][x][y] < c:
    continue
  l, r = c+1, -(-c//k)*k
  if di == 0:
    if x > 0 and S[x-1][y] == "." and dist[di][x-1][y] > l:
      dist[di][x-1][y] = l
      heapq.heappush(que, (l, di, x-1, y))
  elif di == 1:
    if y > 0 and S[x][y-1] == "." and dist[di][x][y-1] > l:
      dist[di][x][y-1] = l
      heapq.heappush(que, (l, di, x, y-1))
  elif di == 2:
    if x < h-1 and S[x+1][y] == "." and dist[di][x+1][y] > l:
      dist[di][x+1][y] = l
      heapq.heappush(que, (l, di, x+1, y))
  else:
    if y < w-1 and S[x][y+1] == "." and dist[di][x][y+1] > l:
      dist[di][x][y+1] = l
      heapq.heappush(que, (l, di, x, y+1))
      
  if di%2:
    if dist[0][x][y] > r:
      dist[0][x][y] = r
      heapq.heappush(que, (r, 0, x, y))
    if dist[2][x][y] > r:
      dist[2][x][y] = r
      heapq.heappush(que, (r, 2, x, y))
    
  else:
    if dist[1][x][y] > r:
      dist[1][x][y] = r
      heapq.heappush(que, (r, 1, x, y))
    if dist[3][x][y] > r:
      dist[3][x][y] = r
      heapq.heappush(que, (r, 3, x, y))
t = min(dist[0][x2][y2], dist[1][x2][y2], dist[2][x2][y2], dist[3][x2][y2])
if t == float("inf"):
  print(-1)
else:
  ans = -(-t//k)
  print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque

def main():
  h, w, k = map(int, input().split())
  x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
  v1 = x1*(w+1)+y1
  v2 = x2*(w+1)+y2
  C = "".join(input().rstrip()+"@" for _ in range(h))
  dist = [-1 if c=="@" else 10**10 for c in C]
  ans = 0
  que = deque()
  que.append(v1)
  dist[v1] = 0
  while que:
    v = que.popleft()
    if v == v2:
      print(dist[v2])
      exit()
    d = dist[v]+1
    for dr in (-(w+1), -1, w+1, 1):
      for i in range(1, k+1):
        nv = v+dr*i
        if 0 <= nv < h*(w+1):
          if dist[nv] > d:
            dist[nv] = d
            que.append(nv)
          elif dist[nv] == d:
            continue
          else:
            break
        else:
          break
  print(-1)
if __name__ == "__main__":
  main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
import heapq

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
S = [input().rstrip() for _ in range(h)]
dist = [[[float("inf")]*w  for i in range(h)] for _ in range(4)]
que = []
que.append((0, 0, x1, y1))
dist[0][x1][y1] = 0
  
while que:
  c, di, x, y = heapq.heappop(que)
  if dist[di][x][y] < c:
    continue
  l, r = c+1, -(-c//k)*k
  if di == 0:
    if x > 0 and S[x-1][y] == "." and dist[di][x-1][y] > l:
      dist[di][x-1][y] = l
      heapq.heappush(que, (l, di, x-1, y))
  elif di == 1:
    if y > 0 and S[x][y-1] == "." and dist[di][x][y-1] > l:
      dist[di][x][y-1] = l
      heapq.heappush(que, (l, di, x, y-1))
  elif di == 2:
    if x < h-1 and S[x+1][y] == "." and dist[di][x+1][y] > l:
      dist[di][x+1][y] = l
      heapq.heappush(que, (l, di, x+1, y))
  else:
    if y < w-1 and S[x][y+1] == "." and dist[di][x][y+1] > l:
      dist[di][x][y+1] = l
      heapq.heappush(que, (l, di, x, y+1))
      
  if di%2:
    if dist[0][x][y] > r:
      dist[0][x][y] = r
      heapq.heappush(que, (r, 0, x, y))
    if dist[2][x][y] > r:
      dist[2][x][y] = r
      heapq.heappush(que, (r, 2, x, y))
    
  else:
    if dist[1][x][y] > r:
      dist[1][x][y] = r
      heapq.heappush(que, (r, 1, x, y))
    if dist[3][x][y] > r:
      dist[3][x][y] = r
      heapq.heappush(que, (r, 3, x, y))
t = min(dist[0][x2][y2], dist[1][x2][y2], dist[2][x2][y2], dist[3][x2][y2])
if t == float("inf"):
  print(-1)
else:
  ans = -(-t//k)
  print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
from collections import deque

def main():
  h, w, k = map(int, input().split())
  x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
  v1 = x1*(w+1)+y1
  v2 = x2*(w+1)+y2
  C = "".join(input().rstrip()+"@" for _ in range(h))
  dist = [-1 if c=="@" else 10**10 for c in C]
  ans = 0
  que = deque()
  que.append(v1)
  dist[v1] = 0
  while que:
    v = que.popleft()
    if v == v2:
      print(dist[v2])
      exit()
    d = dist[v]+1
    for dr in (-(w+1), -1, w+1, 1):
      for i in range(1, k+1):
        nv = v+dr*i
        if 0 <= nv < h*(w+1):
          if dist[nv] > d:
            dist[nv] = d
            que.append(nv)
          elif dist[nv] == d:
            continue
          else:
            break
        else:
          break
  print(-1)
if __name__ == "__main__":
  main()