Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
# 文字列をinput()した場合、末尾に改行が入るので注意
def main():
  h,w,k=map(int,input().split())
  x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
  cmap=[input() for _ in range(h)]
  from heapq import heappop,heappush,heapify
  dv={'w':0,'n':1,'e':2,'s':3}
  inf=float('inf')
  seen=[[[inf]*4 for _ in range(w)] for _ in range(h)]
  todo=[[0,x1,y1,'w']]
  seen[x1][y1][dv['w']]=0
  heapify(todo)
  #d=[[-1]*w for _ in range(h)]
  cnt=1
  while todo:
    c,x,y,v=heappop(todo)
    #print(c,x,y,v)
    if (x,y)==(x2,y2):
      print((c+k-1)//k)
      exit()
      #break
    if v=='w':
      if seen[x][y][dv['n']]>k*((c+k-1)//k):
        heappush(todo,[k*((c+k-1)//k),x,y,'n'])
        seen[x][y][dv['n']]=k*((c+k-1)//k)
      if y>0 and cmap[x][y-1]!='@' and seen[x][y-1][dv['w']]>c+1:
        heappush(todo,[c+1,x,y-1,'w'])
        seen[x][y-1][dv['w']]=c+1
    elif v=='e':
      if seen[x][y][dv['s']]>k*((c+k-1)//k):
        heappush(todo,[k*((c+k-1)//k),x,y,'s'])
        seen[x][y][dv['s']]=k*((c+k-1)//k)
      if y<w-1 and cmap[x][y+1]!='@' and seen[x][y+1][dv['e']]>c+1:
        heappush(todo,[c+1,x,y+1,'e'])
        seen[x][y+1][dv['e']]=c+1
    elif v=='n':
      if seen[x][y][dv['e']]>k*((c+k-1)//k):
        heappush(todo,[k*((c+k-1)//k),x,y,'e'])
        seen[x][y][dv['e']]=k*((c+k-1)//k)
      if x>0 and cmap[x-1][y]!='@' and seen[x-1][y][dv['n']]>c+1:
        heappush(todo,[c+1,x-1,y,'n'])
        seen[x-1][y][dv['n']]=c+1
    elif v=='s':
      if seen[x][y][dv['w']]>k*((c+k-1)//k):
        heappush(todo,[k*((c+k-1)//k),x,y,'w'])
        seen[x][y][dv['w']]=k*((c+k-1)//k)
      if x<h-1 and cmap[x+1][y]!='@' and seen[x+1][y][dv['s']]>c+1:
        heappush(todo,[c+1,x+1,y,'s'])
        seen[x+1][y][dv['s']]=c+1

  print(-1)
  #for si in seen:
  #  print([min(sij) for sij in si])

if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())

Fixed submission:
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
cmap=[input() for _ in range(h)]
inf=float('inf')
seen=[[[(inf,inf)]*4 for _ in range(w)] for _ in range(h)]
D=[(-1,0),(0,1),(1,0),(0,-1)]# 上:0, 右:1, 下:2, 左:3
q=deque()
for d in range(4):
  seen[x1][y1][d]=(1,0)
  q.append((x1, y1, d, 1, 0)) # (x, y, 進行方向[d], 移動回数[c], 進行済マス数[k])
while q:
  x,y,d,c,k_=q.popleft()
  # nx, ny: 次の座標
  # nd: 次の進行方向
  # nc: 次の移動回数
  # nk: 次の進行済マス数
  for nd in range(4):
    if nd==d:
      dx,dy=D[nd]
      nk=1 if k_==k else k_+1
      nc=c+1 if k_==k else c
    else:
      dx,dy=0,0
      nk=0
      nc=c+1
    nx=x+dx;ny=y+dy
    if 0<=nx<h and 0<=ny<w and cmap[nx][ny]!='@' and seen[nx][ny][nd]>(nc,nk):
      seen[nx][ny][nd]=(nc,nk)
      if nc==c: # 同一方向に進むケースは次のループで一番はじめに処理する。
        q.appendleft((nx,ny,nd,nc,nk))
      else:
        q.append((nx,ny,nd,nc,nk))
ans=inf
for d in range(4):
  ans=min(ans,seen[x2][y2][d][0])
ans=-1 if ans==inf else ans
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
# 文字列をinput()した場合、末尾に改行が入るので注意
def main():
  h,w,k=map(int,input().split())
  x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
  cmap=[input() for _ in range(h)]
  from heapq import heappop,heappush,heapify
  dv={'w':0,'n':1,'e':2,'s':3}
  inf=float('inf')
  seen=[[[inf]*4 for _ in range(w)] for _ in range(h)]
  todo=[[0,x1,y1,'w']]
  seen[x1][y1][dv['w']]=0
  heapify(todo)
  #d=[[-1]*w for _ in range(h)]
  cnt=1
  while todo:
    c,x,y,v=heappop(todo)
    #print(c,x,y,v)
    if (x,y)==(x2,y2):
      print((c+k-1)//k)
      exit()
      #break
    if v=='w':
      if seen[x][y][dv['n']]>k*((c+k-1)//k):
        heappush(todo,[k*((c+k-1)//k),x,y,'n'])
        seen[x][y][dv['n']]=k*((c+k-1)//k)
      if y>0 and cmap[x][y-1]!='@' and seen[x][y-1][dv['w']]>c+1:
        heappush(todo,[c+1,x,y-1,'w'])
        seen[x][y-1][dv['w']]=c+1
    elif v=='e':
      if seen[x][y][dv['s']]>k*((c+k-1)//k):
        heappush(todo,[k*((c+k-1)//k),x,y,'s'])
        seen[x][y][dv['s']]=k*((c+k-1)//k)
      if y<w-1 and cmap[x][y+1]!='@' and seen[x][y+1][dv['e']]>c+1:
        heappush(todo,[c+1,x,y+1,'e'])
        seen[x][y+1][dv['e']]=c+1
    elif v=='n':
      if seen[x][y][dv['e']]>k*((c+k-1)//k):
        heappush(todo,[k*((c+k-1)//k),x,y,'e'])
        seen[x][y][dv['e']]=k*((c+k-1)//k)
      if x>0 and cmap[x-1][y]!='@' and seen[x-1][y][dv['n']]>c+1:
        heappush(todo,[c+1,x-1,y,'n'])
        seen[x-1][y][dv['n']]=c+1
    elif v=='s':
      if seen[x][y][dv['w']]>k*((c+k-1)//k):
        heappush(todo,[k*((c+k-1)//k),x,y,'w'])
        seen[x][y][dv['w']]=k*((c+k-1)//k)
      if x<h-1 and cmap[x+1][y]!='@' and seen[x+1][y][dv['s']]>c+1:
        heappush(todo,[c+1,x+1,y,'s'])
        seen[x+1][y][dv['s']]=c+1

  print(-1)
  #for si in seen:
  #  print([min(sij) for sij in si])

if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())

Fixed submission:
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
cmap=[input() for _ in range(h)]
inf=float('inf')
seen=[[[(inf,inf)]*4 for _ in range(w)] for _ in range(h)]
D=[(-1,0),(0,1),(1,0),(0,-1)]# 上:0, 右:1, 下:2, 左:3
q=deque()
for d in range(4):
  seen[x1][y1][d]=(1,0)
  q.append((x1, y1, d, 1, 0)) # (x, y, 進行方向[d], 移動回数[c], 進行済マス数[k])
while q:
  x,y,d,c,k_=q.popleft()
  # nx, ny: 次の座標
  # nd: 次の進行方向
  # nc: 次の移動回数
  # nk: 次の進行済マス数
  for nd in range(4):
    if nd==d:
      dx,dy=D[nd]
      nk=1 if k_==k else k_+1
      nc=c+1 if k_==k else c
    else:
      dx,dy=0,0
      nk=0
      nc=c+1
    nx=x+dx;ny=y+dy
    if 0<=nx<h and 0<=ny<w and cmap[nx][ny]!='@' and seen[nx][ny][nd]>(nc,nk):
      seen[nx][ny][nd]=(nc,nk)
      if nc==c: # 同一方向に進むケースは次のループで一番はじめに処理する。
        q.appendleft((nx,ny,nd,nc,nk))
      else:
        q.append((nx,ny,nd,nc,nk))
ans=inf
for d in range(4):
  ans=min(ans,seen[x2][y2][d][0])
ans=-1 if ans==inf else ans
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
cmap=[input() for _ in range(h)]
from math import ceil
from heapq import heappop,heappush,heapify
dv={'w':0,'n':1,'e':2,'s':3}
seen=[[[0]*4 for _ in range(w)] for _ in range(h)]
todo=[[0,x1,y1,'w'],[0,x1,y1,'n'],[0,x1,y1,'e'],[0,x1,y1,'s']]

heapify(todo)
d=[[0]*w for _ in range(h)]
while todo:
  c,x,y,v=heappop(todo)
  if seen[x][y]==1:continue
  seen[x][y][dv[v]]=1
  d[x][y]=c
  if (x,y)==(x2,y2):
    print(ceil(c))
    #for di in d:
    #  print(di)
    exit()
  #print(c,x,y,v)
  if v=='w':
    if seen[x][y][dv['n']]==0 and cmap[x][y]!='@':heappush(todo,[ceil(c),x,y,'n'])
    if seen[x][y][dv['s']]==0 and cmap[x][y]!='@':heappush(todo,[ceil(c),x,y,'s'])
    while y>0 and cmap[x][y-1]!='@':
      y-=1
      c+=1/k
      if seen[x][y][dv['w']]==0:heappush(todo,[c,x,y,'w'])
  elif v=='e':
    if seen[x][y][dv['n']]==0 and cmap[x][y]!='@':heappush(todo,[ceil(c),x,y,'n'])
    if seen[x][y][dv['s']]==0 and cmap[x][y]!='@':heappush(todo,[ceil(c),x,y,'s'])
    while y<w-1 and cmap[x][y+1]!='@':
      y+=1
      c+=1/k
      if seen[x][y][dv['e']]==0:heappush(todo,[c,x,y,'e'])
  elif v=='n':
    if seen[x][y][dv['w']]==0 and cmap[x][y]!='@':heappush(todo,[ceil(c),x,y,'w'])
    if seen[x][y][dv['e']]==0 and cmap[x][y]!='@':heappush(todo,[ceil(c),x,y,'e'])
    while x>0 and cmap[x-1][y]!='@':
      x-=1
      c+=1/k
      if seen[x][y][dv['n']]==0:heappush(todo,[c,x,y,'n'])
  elif v=='s':
    if seen[x][y][dv['w']]==0 and cmap[x][y]!='@':heappush(todo,[ceil(c),x,y,'w'])
    if seen[x][y][dv['e']]==0 and cmap[x][y]!='@':heappush(todo,[ceil(c),x,y,'e'])
    while x<h-1 and cmap[x+1][y]!='@':
      x+=1
      c+=1/k
      if seen[x][y][dv['s']]==0:heappush(todo,[c,x,y,'s'])

print(-1)
#print(d)


Fixed submission:
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
cmap=[input() for _ in range(h)]
inf=float('inf')
seen=[[[(inf,inf)]*4 for _ in range(w)] for _ in range(h)]
D=[(-1,0),(0,1),(1,0),(0,-1)]# 上:0, 右:1, 下:2, 左:3
q=deque()
for d in range(4):
  seen[x1][y1][d]=(1,0)
  q.append((x1, y1, d, 1, 0)) # (x, y, 進行方向[d], 移動回数[c], 進行済マス数[k])
while q:
  x,y,d,c,k_=q.popleft()
  # nx, ny: 次の座標
  # nd: 次の進行方向
  # nc: 次の移動回数
  # nk: 次の進行済マス数
  for nd in range(4):
    if nd==d:
      dx,dy=D[nd]
      nk=1 if k_==k else k_+1
      nc=c+1 if k_==k else c
    else:
      dx,dy=0,0
      nk=0
      nc=c+1
    nx=x+dx;ny=y+dy
    if 0<=nx<h and 0<=ny<w and cmap[nx][ny]!='@' and seen[nx][ny][nd]>(nc,nk):
      seen[nx][ny][nd]=(nc,nk)
      if nc==c: # 同一方向に進むケースは次のループで一番はじめに処理する。
        q.appendleft((nx,ny,nd,nc,nk))
      else:
        q.append((nx,ny,nd,nc,nk))
ans=inf
for d in range(4):
  ans=min(ans,seen[x2][y2][d][0])
ans=-1 if ans==inf else ans
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
c=[input() for _ in range(h)]
"""
ha=[]
for i in range(h):
  for j in range(w):
    if c[i][j]=='@':
      ha.append([i,j])
"""
from collections import deque
seen=[[0]*w for _ in range(h)]
todo=deque([[0,x1,y1]])
seen[x1][x2]=1
while todo:
  t,x,y=todo.popleft()

  if x==x2 and y==y2:
    print(t)
    exit(0)
  if x>0:
    for xi in range(x-1,max(x-k,0)-1,-1):
      if c[xi][y]=='@':break
      if seen[xi][y]==1:continue
      seen[xi][y]=1
      todo.append([t+1,xi,y])
  if x<h-1:
    for xi in range(x+1,min(x+k,h-1)+1):
      if c[xi][y]=='@':break
      if seen[xi][y]==1:continue
      seen[xi][y]=1
      todo.append([t+1,xi,y])
  if y>0:
    for yi in range(y-1,max(y-k,0)-1,-1):
      if c[x][yi]=='@':break
      if seen[x][yi]==1:continue
      seen[x][yi]=1
      todo.append([t+1,x,yi])
  if y<w-1:
    for yi in range(y+1,min(y+k,w-1)+1):
      if c[x][yi]=='@':break
      if seen[x][yi]==1:continue
      seen[x][yi]=1
      todo.append([t+1,x,yi])
print(-1)


Fixed submission:
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
cmap=[input() for _ in range(h)]
inf=float('inf')
seen=[[[(inf,inf)]*4 for _ in range(w)] for _ in range(h)]
D=[(-1,0),(0,1),(1,0),(0,-1)]# 上:0, 右:1, 下:2, 左:3
q=deque()
for d in range(4):
  seen[x1][y1][d]=(1,0)
  q.append((x1, y1, d, 1, 0)) # (x, y, 進行方向[d], 移動回数[c], 進行済マス数[k])
while q:
  x,y,d,c,k_=q.popleft()
  # nx, ny: 次の座標
  # nd: 次の進行方向
  # nc: 次の移動回数
  # nk: 次の進行済マス数
  for nd in range(4):
    if nd==d:
      dx,dy=D[nd]
      nk=1 if k_==k else k_+1
      nc=c+1 if k_==k else c
    else:
      dx,dy=0,0
      nk=0
      nc=c+1
    nx=x+dx;ny=y+dy
    if 0<=nx<h and 0<=ny<w and cmap[nx][ny]!='@' and seen[nx][ny][nd]>(nc,nk):
      seen[nx][ny][nd]=(nc,nk)
      if nc==c: # 同一方向に進むケースは次のループで一番はじめに処理する。
        q.appendleft((nx,ny,nd,nc,nk))
      else:
        q.append((nx,ny,nd,nc,nk))
ans=inf
for d in range(4):
  ans=min(ans,seen[x2][y2][d][0])
ans=-1 if ans==inf else ans
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
c=[input() for _ in range(h)]
"""
ha=[]
for i in range(h):
  for j in range(w):
    if c[i][j]=='@':
      ha.append([i,j])
"""
from collections import deque
seen=[[0]*w for _ in range(h)]
todo=deque([[0,x1,y1]])
seen[x1][x2]=1
while todo:
  t,x,y=todo.popleft()

  if x==x2 and y==y2:
    print(t)
    exit(0)
  if x>0:
    for xi in range(x-1,max(x-k,0)-1,-1):
      if c[xi][y]=='@':break
      if seen[xi][y]==1:continue
      seen[xi][y]=1
      todo.append([t+1,xi,y])
  if x<h-1:
    for xi in range(x+1,min(x+k,h-1)+1):
      if c[xi][y]=='@':break
      if seen[xi][y]==1:continue
      seen[xi][y]=1
      todo.append([t+1,xi,y])
  if y>0:
    for yi in range(y-1,max(y-k,0)-1,-1):
      if c[x][yi]=='@':break
      if seen[x][yi]==1:continue
      seen[x][yi]=1
      todo.append([t+1,x,yi])
  if y<w-1:
    for yi in range(y+1,min(y+k,w-1)+1):
      if c[x][yi]=='@':break
      if seen[x][yi]==1:continue
      seen[x][yi]=1
      todo.append([t+1,x,yi])
print(-1)

Fixed submission:
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
cmap=[input() for _ in range(h)]
inf=float('inf')
seen=[[[(inf,inf)]*4 for _ in range(w)] for _ in range(h)]
D=[(-1,0),(0,1),(1,0),(0,-1)]# 上:0, 右:1, 下:2, 左:3
q=deque()
for d in range(4):
  seen[x1][y1][d]=(1,0)
  q.append((x1, y1, d, 1, 0)) # (x, y, 進行方向[d], 移動回数[c], 進行済マス数[k])
while q:
  x,y,d,c,k_=q.popleft()
  # nx, ny: 次の座標
  # nd: 次の進行方向
  # nc: 次の移動回数
  # nk: 次の進行済マス数
  for nd in range(4):
    if nd==d:
      dx,dy=D[nd]
      nk=1 if k_==k else k_+1
      nc=c+1 if k_==k else c
    else:
      dx,dy=0,0
      nk=0
      nc=c+1
    nx=x+dx;ny=y+dy
    if 0<=nx<h and 0<=ny<w and cmap[nx][ny]!='@' and seen[nx][ny][nd]>(nc,nk):
      seen[nx][ny][nd]=(nc,nk)
      if nc==c: # 同一方向に進むケースは次のループで一番はじめに処理する。
        q.appendleft((nx,ny,nd,nc,nk))
      else:
        q.append((nx,ny,nd,nc,nk))
ans=inf
for d in range(4):
  ans=min(ans,seen[x2][y2][d][0])
ans=-1 if ans==inf else ans
print(ans)