Buggy python submission (verdict: Time Limit Exceeded):
#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[[inf for _ in range(4)] for _ in range(w)] for _ in range(h)]
seen[x1][y1] = [0,0,0,0]

dire = [[1,0],[-1,0],[0,1],[0,-1]]
def add(x,y,di,s):
  dx,dy = dire[di]
  if 0 <= x+dx < h and 0 <= y+dy < w:
    if raw[x+dx][y+dy] == '.' and seen[x+dx][y+dy][di] > s:
      now.append((s,x+dx,y+dy,di))
      seen[x+dx][y+dy][di] = s
def turn(x,y,di,s):
  dx,dy = dire[di]
  if seen[x][y][di] > s:
    nex.append((s,x,y,di))
    seen[x][y][di] = s

nex = [[0,x1,y1,d] for d in range(4)]
while nex:
  now = nex[:]
  nex = []
  for i in range(k):
    last = now[:]
    now = []
    for sxydi in last:
      s,x,y,di = sxydi
      if seen[x][y][di] < s:
        continue
      if x == x2 and y == y2:
        print(s)
        exit()
      add(x,y,di,s+1-int(bool(i)))
      for d in range(4):
        if di != d:
          turn(x,y,d,s)
  for xx in now:
    nex.append(xx)
print(-1)

Fixed submission:
#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[inf for _ in range(w)] for _ in range(h)]
seen[x1][y1] = 0
from heapq import heappush as push
from heapq import heappop as pop
now = [[0,x1,y1]]

while now:
  s,x,y = pop(now)
  if x == x2 and y == y2:
    print(s)
    exit()
  for i in range(1,k+1):
    if x-i == -1 or raw[x-i][y] == '@' or seen[x-i][y] < s+1:
      break
    if seen[x-i][y] != s+1:
      seen[x-i][y] = s+1
      push(now,[s+1,x-i,y])
  for i in range(1,k+1):
    if y-i == -1 or raw[x][y-i] == '@' or seen[x][y-i] < s+1:
      break
    if seen[x][y-i] != s+1:
      seen[x][y-i] = s+1
      push(now,[s+1,x,y-i])
  for i in range(1,k+1):
    if x+i == h or raw[x+i][y] == '@' or seen[x+i][y] < s+1:
      break
    if seen[x+i][y] != s+1:
      seen[x+i][y] = s+1
      push(now,[s+1,x+i,y])
  for i in range(1,k+1):
    if y+i == w or raw[x][y+i] == '@' or seen[x][y+i] < s+1:
      break
    if seen[x][y+i] != s+1:
      seen[x][y+i] = s+1
      push(now,[s+1,x,y+i])
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[[inf for _ in range(4)] for _ in range(w)] for _ in range(h)]
seen[x1][y1] = [0,0,0,0]

dire = [[1,0],[-1,0],[0,1],[0,-1]]
def add(x,y,di,s):
  dx,dy = dire[di]
  if 0 <= x+dx < h and 0 <= y+dy < w:
    if raw[x+dx][y+dy] == '.' and seen[x+dx][y+dy][di] > s:
      now.append([s,x+dx,y+dy,di])
      seen[x+dx][y+dy][di] = s
def turn(x,y,di,s):
  dx,dy = dire[di]
  if seen[x][y][di] > s:
    nex.append([s,x,y,di])
    seen[x][y][di] = s

nex = [[0,x1,y1,d] for d in range(4)]
while nex:
  now = nex[:]
  nex = []
  for i in range(k):
    last = now[:]
    now = []
    for sxydi in last:
      s,x,y,di = sxydi
      if seen[x][y][di] < s:
        continue
      if x == x2 and y == y2:
        print(s)
        exit()
      add(x,y,di,s+1-int(bool(i)))
      for d in range(4):
        if di != d:
          turn(x,y,d,s)
  for xx in now:
    nex.append(xx)
print(-1)

Fixed submission:
#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[inf for _ in range(w)] for _ in range(h)]
seen[x1][y1] = 0
from heapq import heappush as push
from heapq import heappop as pop
now = [[0,x1,y1]]

while now:
  s,x,y = pop(now)
  if x == x2 and y == y2:
    print(s)
    exit()
  for i in range(1,k+1):
    if x-i == -1 or raw[x-i][y] == '@' or seen[x-i][y] < s+1:
      break
    if seen[x-i][y] != s+1:
      seen[x-i][y] = s+1
      push(now,[s+1,x-i,y])
  for i in range(1,k+1):
    if y-i == -1 or raw[x][y-i] == '@' or seen[x][y-i] < s+1:
      break
    if seen[x][y-i] != s+1:
      seen[x][y-i] = s+1
      push(now,[s+1,x,y-i])
  for i in range(1,k+1):
    if x+i == h or raw[x+i][y] == '@' or seen[x+i][y] < s+1:
      break
    if seen[x+i][y] != s+1:
      seen[x+i][y] = s+1
      push(now,[s+1,x+i,y])
  for i in range(1,k+1):
    if y+i == w or raw[x][y+i] == '@' or seen[x][y+i] < s+1:
      break
    if seen[x][y+i] != s+1:
      seen[x][y+i] = s+1
      push(now,[s+1,x,y+i])
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[[inf for _ in range(4)] for _ in range(w)] for _ in range(h)]
seen[x1][y1] = [0,0,0,0]

dire = [[1,0],[-1,0],[0,1],[0,-1]]
def add(x,y,di,s):
  dx,dy = dire[di]
  if 0 <= x+dx < h and 0 <= y+dy < w:
    if raw[x+dx][y+dy] == '.' and seen[x+dx][y+dy][di] > s:
      now.append([s,x+dx,y+dy,di])
      seen[x+dx][y+dy][di] = s
def turn(x,y,di,s):
  dx,dy = dire[di]
  if seen[x][y][di] > s:
    nex.append([s,x,y,di])
    seen[x][y][di] = s

nex = [[0,x1,y1,d] for d in range(4)]
while nex:
  now = nex
  nex = []
  for i in range(k):
    last = now
    now = []
    for sxydi in last:
      s,x,y,di = sxydi
      if seen[x][y][di] < s:
        continue
      if x == x2 and y == y2:
        print(s)
        exit()
      add(x,y,di,s+1-int(bool(i)))
      for d in range(4):
        if di != d:
          turn(x,y,d,s)
  nex += now
print(-1)

Fixed submission:
#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[inf for _ in range(w)] for _ in range(h)]
seen[x1][y1] = 0
from heapq import heappush as push
from heapq import heappop as pop
now = [[0,x1,y1]]

while now:
  s,x,y = pop(now)
  if x == x2 and y == y2:
    print(s)
    exit()
  for i in range(1,k+1):
    if x-i == -1 or raw[x-i][y] == '@' or seen[x-i][y] < s+1:
      break
    if seen[x-i][y] != s+1:
      seen[x-i][y] = s+1
      push(now,[s+1,x-i,y])
  for i in range(1,k+1):
    if y-i == -1 or raw[x][y-i] == '@' or seen[x][y-i] < s+1:
      break
    if seen[x][y-i] != s+1:
      seen[x][y-i] = s+1
      push(now,[s+1,x,y-i])
  for i in range(1,k+1):
    if x+i == h or raw[x+i][y] == '@' or seen[x+i][y] < s+1:
      break
    if seen[x+i][y] != s+1:
      seen[x+i][y] = s+1
      push(now,[s+1,x+i,y])
  for i in range(1,k+1):
    if y+i == w or raw[x][y+i] == '@' or seen[x][y+i] < s+1:
      break
    if seen[x][y+i] != s+1:
      seen[x][y+i] = s+1
      push(now,[s+1,x,y+i])
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**7
seen = [[[inf for _ in range(4)] for _ in range(w)] for _ in range(h)]
seen[x1][y1] = [0,0,0,0]

dire = [[1,0],[-1,0],[0,1],[0,-1]]
def add(x,y,di,I,J,s):
  dx,dy = dire[di]
  if J == 0:
    if 0 <= x+dx < h and 0 <= y+dy < w:
      if raw[x+dx][y+dy] == '.' and seen[x+dx][y+dy][di] > s+I:
        #print(s+I,'&&',x+dx,y+dy,di)
        now.append([s+I,x+dx,y+dy,di])
        seen[x+dx][y+dy][di] = s+I
  else:
    if seen[x][y][di] > s+I:
      nex.append([s+I,x,y,di])
      seen[x][y][di] = s+I

nex = [[0,x1,y1,d] for d in range(4)]
while nex:
  now = nex
  nex = []
  for i in range(k):
    last = now
    now = []
    for sxydi in last:
      s,x,y,di = sxydi
      if seen[x][y][di] < s:
        continue
      if x == x2 and y == y2:
        print(s)
        #for xx in seen:
          #print(xx)
        exit()
      #print('&',s,x,y,di)
      add(x,y,di,1-int(bool(i)),0,s)
      for d in range(4):
        add(x,y,d,0,1,s)
    #print(now)
  #print('#',nex)
  nex += now
  #print('#',nex)
print(-1)
#for xx in seen:
  #print(xx)

Fixed submission:
#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[inf for _ in range(w)] for _ in range(h)]
seen[x1][y1] = 0
from heapq import heappush as push
from heapq import heappop as pop
now = [[0,x1,y1]]

while now:
  s,x,y = pop(now)
  if x == x2 and y == y2:
    print(s)
    exit()
  for i in range(1,k+1):
    if x-i == -1 or raw[x-i][y] == '@' or seen[x-i][y] < s+1:
      break
    if seen[x-i][y] != s+1:
      seen[x-i][y] = s+1
      push(now,[s+1,x-i,y])
  for i in range(1,k+1):
    if y-i == -1 or raw[x][y-i] == '@' or seen[x][y-i] < s+1:
      break
    if seen[x][y-i] != s+1:
      seen[x][y-i] = s+1
      push(now,[s+1,x,y-i])
  for i in range(1,k+1):
    if x+i == h or raw[x+i][y] == '@' or seen[x+i][y] < s+1:
      break
    if seen[x+i][y] != s+1:
      seen[x+i][y] = s+1
      push(now,[s+1,x+i,y])
  for i in range(1,k+1):
    if y+i == w or raw[x][y+i] == '@' or seen[x][y+i] < s+1:
      break
    if seen[x][y+i] != s+1:
      seen[x][y+i] = s+1
      push(now,[s+1,x,y+i])
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**7
seen = [[[inf for _ in range(4)] for _ in range(w)] for _ in range(h)]
seen[x1][y1] = [0,0,0,0]

dire = [[1,0],[-1,0],[0,1],[0,-1]]
def add(x,y,di,I,J,s):
  dx,dy = dire[di]
  if J == 0:
    if 0 <= x+dx < h and 0 <= y+dy < w:
      if raw[x+dx][y+dy] == '.' and seen[x+dx][y+dy][di] > s+I:
        now.append([s+I,x+dx,y+dy,di])
        seen[x+dx][y+dy][di] = s+I
  else:
    if seen[x][y][di] > s+I:
      nex.append([s+I,x,y,di])
      seen[x][y][di] = s+I

nex = [[0,x1,y1,d] for d in range(4)]
while nex:
  now = nex
  nex = []
  for i in range(k):
    last = now
    now = []
    for sxydi in last:
      s,x,y,di = sxydi
      if seen[x][y][di] < s:
        continue
      if x == x2 and y == y2:
        print(s)
        exit()
      add(x,y,di,1-int(bool(i)),0,s)
      for d in range(4):
        if di != d:
          add(x,y,d,0,1,s)
  nex += now
print(-1)

Fixed submission:
#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[inf for _ in range(w)] for _ in range(h)]
seen[x1][y1] = 0
from heapq import heappush as push
from heapq import heappop as pop
now = [[0,x1,y1]]

while now:
  s,x,y = pop(now)
  if x == x2 and y == y2:
    print(s)
    exit()
  for i in range(1,k+1):
    if x-i == -1 or raw[x-i][y] == '@' or seen[x-i][y] < s+1:
      break
    if seen[x-i][y] != s+1:
      seen[x-i][y] = s+1
      push(now,[s+1,x-i,y])
  for i in range(1,k+1):
    if y-i == -1 or raw[x][y-i] == '@' or seen[x][y-i] < s+1:
      break
    if seen[x][y-i] != s+1:
      seen[x][y-i] = s+1
      push(now,[s+1,x,y-i])
  for i in range(1,k+1):
    if x+i == h or raw[x+i][y] == '@' or seen[x+i][y] < s+1:
      break
    if seen[x+i][y] != s+1:
      seen[x+i][y] = s+1
      push(now,[s+1,x+i,y])
  for i in range(1,k+1):
    if y+i == w or raw[x][y+i] == '@' or seen[x][y+i] < s+1:
      break
    if seen[x][y+i] != s+1:
      seen[x][y+i] = s+1
      push(now,[s+1,x,y+i])
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[[inf for _ in range(4)] for _ in range(w)] for _ in range(h)]
seen[x1][y1] = [0,0,0,0]

dire = [[1,0],[-1,0],[0,1],[0,-1]]
def add(x,y,di,I,J,s):
  dx,dy = dire[di]
  if J == 0:
    if 0 <= x+dx < h and 0 <= y+dy < w:
      if raw[x+dx][y+dy] == '.' and seen[x+dx][y+dy][di] > s+I:
        now.append([s+I,x+dx,y+dy,di])
        seen[x+dx][y+dy][di] = s+I
  else:
    if seen[x][y][di] > s+I:
      nex.append([s+I,x,y,di])
      seen[x][y][di] = s+I

nex = [[0,x1,y1,d] for d in range(4)]
while nex:
  now = nex[:]
  nex = []
  for i in range(k):
    last = now[:]
    now = []
    for sxydi in last:
      s,x,y,di = sxydi
      if seen[x][y][di] < s:
        continue
      if x == x2 and y == y2:
        print(s)
        exit()
      add(x,y,di,1-int(bool(i)),0,s)
      for d in range(4):
        if di != d:
          add(x,y,d,0,1,s)
  nex += now
print(-1)

Fixed submission:
#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[inf for _ in range(w)] for _ in range(h)]
seen[x1][y1] = 0
from heapq import heappush as push
from heapq import heappop as pop
now = [[0,x1,y1]]

while now:
  s,x,y = pop(now)
  if x == x2 and y == y2:
    print(s)
    exit()
  for i in range(1,k+1):
    if x-i == -1 or raw[x-i][y] == '@' or seen[x-i][y] < s+1:
      break
    if seen[x-i][y] != s+1:
      seen[x-i][y] = s+1
      push(now,[s+1,x-i,y])
  for i in range(1,k+1):
    if y-i == -1 or raw[x][y-i] == '@' or seen[x][y-i] < s+1:
      break
    if seen[x][y-i] != s+1:
      seen[x][y-i] = s+1
      push(now,[s+1,x,y-i])
  for i in range(1,k+1):
    if x+i == h or raw[x+i][y] == '@' or seen[x+i][y] < s+1:
      break
    if seen[x+i][y] != s+1:
      seen[x+i][y] = s+1
      push(now,[s+1,x+i,y])
  for i in range(1,k+1):
    if y+i == w or raw[x][y+i] == '@' or seen[x][y+i] < s+1:
      break
    if seen[x][y+i] != s+1:
      seen[x][y+i] = s+1
      push(now,[s+1,x,y+i])
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[[inf for _ in range(4)] for _ in range(w)] for _ in range(h)]
seen[x1][y1] = [0,0,0,0]

dire = [[1,0],[-1,0],[0,1],[0,-1]]
def add(x,y,di,I,J,s):
  dx,dy = dire[di]
  if J == 0:
    if 0 <= x+dx < h and 0 <= y+dy < w:
      if raw[x+dx][y+dy] == '.' and seen[x+dx][y+dy][di] > s+I:
        now.append([s+I,x+dx,y+dy,di])
        seen[x+dx][y+dy][di] = s+I
  else:
    if seen[x][y][di] > s+I:
      nex.append([s+I,x,y,di])
      seen[x][y][di] = s+I

nex = [[0,x1,y1,d] for d in range(4)]
while nex:
  now = nex
  nex = []
  for i in range(k):
    last = now
    now = []
    for sxydi in last:
      s,x,y,di = sxydi
      if seen[x][y][di] < s:
        continue
      if x == x2 and y == y2:
        print(s)
        exit()
      add(x,y,di,1-int(bool(i)),0,s)
      for d in range(4):
        if di != d:
          add(x,y,d,0,1,s)
  nex += now
print(-1)

Fixed submission:
#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[inf for _ in range(w)] for _ in range(h)]
seen[x1][y1] = 0
from heapq import heappush as push
from heapq import heappop as pop
now = [[0,x1,y1]]

while now:
  s,x,y = pop(now)
  if x == x2 and y == y2:
    print(s)
    exit()
  for i in range(1,k+1):
    if x-i == -1 or raw[x-i][y] == '@' or seen[x-i][y] < s+1:
      break
    if seen[x-i][y] != s+1:
      seen[x-i][y] = s+1
      push(now,[s+1,x-i,y])
  for i in range(1,k+1):
    if y-i == -1 or raw[x][y-i] == '@' or seen[x][y-i] < s+1:
      break
    if seen[x][y-i] != s+1:
      seen[x][y-i] = s+1
      push(now,[s+1,x,y-i])
  for i in range(1,k+1):
    if x+i == h or raw[x+i][y] == '@' or seen[x+i][y] < s+1:
      break
    if seen[x+i][y] != s+1:
      seen[x+i][y] = s+1
      push(now,[s+1,x+i,y])
  for i in range(1,k+1):
    if y+i == w or raw[x][y+i] == '@' or seen[x][y+i] < s+1:
      break
    if seen[x][y+i] != s+1:
      seen[x][y+i] = s+1
      push(now,[s+1,x,y+i])
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[[inf for _ in range(4)] for _ in range(w)] for _ in range(h)]
seen[x1][y1] = [0,0,0,0]

dire = [[1,0],[-1,0],[0,1],[0,-1]]
def add(x,y,di,I,J,s):
  dx,dy = dire[di]
  if J == 0:
    if 0 <= x+dx < h and 0 <= y+dy < w:
      if raw[x+dx][y+dy] == '.' and seen[x+dx][y+dy][di] > s+I:
        now.append([s+I,x+dx,y+dy,di])
        seen[x+dx][y+dy][di] = s+I
  else:
    if seen[x][y][di] > s+I:
      nex.append([s+I,x,y,di])
      seen[x][y][di] = s+I

nex = [[0,x1,y1,d] for d in range(4)]
while nex:
  now = nex
  nex = []
  for i in range(k):
    last = now
    now = []
    for sxydi in last:
      s,x,y,di = sxydi
      if seen[x][y][di] < s:
        continue
      if x == x2 and y == y2:
        print(s)
        exit()
      add(x,y,di,1-int(bool(i)),0,s)
      for d in range(4):
        if di != d:
          add(x,y,d,0,1,s)
  nex += now
print(-1)

Fixed submission:
#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[inf for _ in range(w)] for _ in range(h)]
seen[x1][y1] = 0
from heapq import heappush as push
from heapq import heappop as pop
now = [[0,x1,y1]]

while now:
  s,x,y = pop(now)
  if x == x2 and y == y2:
    print(s)
    exit()
  for i in range(1,k+1):
    if x-i == -1 or raw[x-i][y] == '@' or seen[x-i][y] < s+1:
      break
    if seen[x-i][y] != s+1:
      seen[x-i][y] = s+1
      push(now,[s+1,x-i,y])
  for i in range(1,k+1):
    if y-i == -1 or raw[x][y-i] == '@' or seen[x][y-i] < s+1:
      break
    if seen[x][y-i] != s+1:
      seen[x][y-i] = s+1
      push(now,[s+1,x,y-i])
  for i in range(1,k+1):
    if x+i == h or raw[x+i][y] == '@' or seen[x+i][y] < s+1:
      break
    if seen[x+i][y] != s+1:
      seen[x+i][y] = s+1
      push(now,[s+1,x+i,y])
  for i in range(1,k+1):
    if y+i == w or raw[x][y+i] == '@' or seen[x][y+i] < s+1:
      break
    if seen[x][y+i] != s+1:
      seen[x][y+i] = s+1
      push(now,[s+1,x,y+i])
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
#解説解答
#23:17
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
a = []
for _ in range(h):
  a.append(input())
inf = 10**10
dijk = [[[inf for _ in range(w)] for _ in range(h)] for _ in range(4)]
import heapq
now = [[0,0,x1,y1]]
# 0up 1down 2right 3left
while now:
  pt,dr,x,y = heapq.heappop(now)
  if x == x2 and y == y2:
    print((pt-1)//k+1)
    break
  if pt > dijk[dr][x][y]:
    continue
    
  for dr2 in range(4):
    if dijk[dr2][x][y] > (pt-1)//k*k+k:
      dijk[dr2][x][y] = (pt-1)//k*k+k
      heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
  
  if dr == 0 and x != 0:
    if a[x-1][y] == '.' and dijk[dr][x-1][y] > pt+1:
      dijk[dr][x-1][y] = pt+1
      heapq.heappush(now,[pt+1,dr,x-1,y])
        
  if dr == 1 and x != h-1:
    if a[x+1][y] == '.' and dijk[dr][x+1][y] > pt+1:
      dijk[dr][x+1][y] = pt+1
      heapq.heappush(now,[pt+1,dr,x+1,y])
        
  if dr == 2 and y != 0:
    if a[x][y-1] == '.' and dijk[dr][x][y-1] > pt+1:
      dijk[dr][x][y-1] = pt+1
      heapq.heappush(now,[pt+1,dr,x,y-1])
  
  if dr == 3 and y != w-1:
    if a[x][y+1] == '.' and dijk[dr][x][y+1] > pt+1:
      dijk[dr][x][y+1] = pt+1
      heapq.heappush(now,[pt+1,dr,x,y+1])
  
  #print(now)
else:
  print(-1)
'''
for x in dijk:
  print('##')
  for y in x:
    print(y)
'''

Fixed submission:
#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[inf for _ in range(w)] for _ in range(h)]
seen[x1][y1] = 0
from heapq import heappush as push
from heapq import heappop as pop
now = [[0,x1,y1]]

while now:
  s,x,y = pop(now)
  if x == x2 and y == y2:
    print(s)
    exit()
  for i in range(1,k+1):
    if x-i == -1 or raw[x-i][y] == '@' or seen[x-i][y] < s+1:
      break
    if seen[x-i][y] != s+1:
      seen[x-i][y] = s+1
      push(now,[s+1,x-i,y])
  for i in range(1,k+1):
    if y-i == -1 or raw[x][y-i] == '@' or seen[x][y-i] < s+1:
      break
    if seen[x][y-i] != s+1:
      seen[x][y-i] = s+1
      push(now,[s+1,x,y-i])
  for i in range(1,k+1):
    if x+i == h or raw[x+i][y] == '@' or seen[x+i][y] < s+1:
      break
    if seen[x+i][y] != s+1:
      seen[x+i][y] = s+1
      push(now,[s+1,x+i,y])
  for i in range(1,k+1):
    if y+i == w or raw[x][y+i] == '@' or seen[x][y+i] < s+1:
      break
    if seen[x][y+i] != s+1:
      seen[x][y+i] = s+1
      push(now,[s+1,x,y+i])
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
#解説解答
#23:17
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
a = []
for _ in range(h):
  a.append(input())
inf = 10**10
dijk = [[[inf for _ in range(w)] for _ in range(h)] for _ in range(4)]
import heapq
now = [[0,0,x1,y1]]
# 0up 1down 2right 3left
while now:
  pt,dr,x,y = heapq.heappop(now)
  if x == x2 and y == y2:
    print((pt-1)//k+1)
    break
  if pt > dijk[dr][x][y]:
    continue
  
  if dr == 0 and x != 0:
    if a[x-1][y] == '.' and dijk[dr][x-1][y] > pt+1:
      dijk[dr][x-1][y] = pt+1
      heapq.heappush(now,[pt+1,dr,x-1,y])
  if dr == 0:
    for dr2 in range(4):
      if dijk[dr2][x][y] > (pt-1)//k*k+k:
        dijk[dr2][x][y] = (pt-1)//k*k+k
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
        
  if dr == 1 and x != h-1:
    if a[x+1][y] == '.' and dijk[dr][x+1][y] > pt+1:
      dijk[dr][x+1][y] = pt+1
      heapq.heappush(now,[pt+1,dr,x+1,y])
  if dr == 1:
    for dr2 in range(4):
      if dijk[dr2][x][y] > (pt-1)//k*k+k:
        dijk[dr2][x][y] = (pt-1)//k*k+k
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
        
  if dr == 2 and y != 0:
    if a[x][y-1] == '.' and dijk[dr][x][y-1] > pt+1:
      dijk[dr][x][y-1] = pt+1
      heapq.heappush(now,[pt+1,dr,x,y-1])
  if dr == 2:
    for dr2 in range(4):
      if dijk[dr2][x][y] > (pt-1)//k*k+k:
        dijk[dr2][x][y] = (pt-1)//k*k+k
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
  
  if dr == 3 and y != w-1:
    if a[x][y+1] == '.' and dijk[dr][x][y+1] > pt+1:
      dijk[dr][x][y+1] = pt+1
      heapq.heappush(now,[pt+1,dr,x,y+1])
  if dr == 3:
    for dr2 in range(4):
      if dijk[dr2][x][y] > (pt-1)//k*k+k:
        dijk[dr2][x][y] = (pt-1)//k*k+k
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
  
  #print(now)
else:
  print(-1)
'''
for x in dijk:
  print('##')
  for y in x:
    print(y)
'''

Fixed submission:
#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[inf for _ in range(w)] for _ in range(h)]
seen[x1][y1] = 0
from heapq import heappush as push
from heapq import heappop as pop
now = [[0,x1,y1]]

while now:
  s,x,y = pop(now)
  if x == x2 and y == y2:
    print(s)
    exit()
  for i in range(1,k+1):
    if x-i == -1 or raw[x-i][y] == '@' or seen[x-i][y] < s+1:
      break
    if seen[x-i][y] != s+1:
      seen[x-i][y] = s+1
      push(now,[s+1,x-i,y])
  for i in range(1,k+1):
    if y-i == -1 or raw[x][y-i] == '@' or seen[x][y-i] < s+1:
      break
    if seen[x][y-i] != s+1:
      seen[x][y-i] = s+1
      push(now,[s+1,x,y-i])
  for i in range(1,k+1):
    if x+i == h or raw[x+i][y] == '@' or seen[x+i][y] < s+1:
      break
    if seen[x+i][y] != s+1:
      seen[x+i][y] = s+1
      push(now,[s+1,x+i,y])
  for i in range(1,k+1):
    if y+i == w or raw[x][y+i] == '@' or seen[x][y+i] < s+1:
      break
    if seen[x][y+i] != s+1:
      seen[x][y+i] = s+1
      push(now,[s+1,x,y+i])
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
#解説解答
#23:17
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
a = []
for _ in range(h):
  a.append(input())
inf = 10**10
dijk = [[[inf for _ in range(w)] for _ in range(h)] for _ in range(4)]
import heapq
now = [[0,0,x1,y1]]
# 0up 1down 2right 3left
while now:
  pt,dr,x,y = heapq.heappop(now)
  if x == x2 and y == y2:
    print((pt-1)//k+1)
    break
  if dijk[dr][x][y] != inf:
    continue
  dijk[dr][x][y] = pt
  
  if dr == 0 and x != 0:
    if a[x-1][y] == '.' and dijk[dr][x-1][y] == inf:
      heapq.heappush(now,[pt+1,dr,x-1,y])
  if dr == 0:
    for dr2 in range(4):
      if dijk[dr2][x][y] == inf:
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
        
  if dr == 1 and x != h-1:
    if a[x+1][y] == '.' and dijk[dr][x+1][y] == inf:
      heapq.heappush(now,[pt+1,dr,x+1,y])
  if dr == 1:
    for dr2 in range(4):
      if dijk[dr2][x][y] == inf:
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
        
  if dr == 2 and y != 0:
    if a[x][y-1] == '.' and dijk[dr][x][y-1] == inf:
      heapq.heappush(now,[pt+1,dr,x,y-1])
  if dr == 2:
    for dr2 in range(4):
      if dijk[dr2][x][y] == inf:
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
  
  if dr == 3 and y != w-1:
    if a[x][y+1] == '.' and dijk[dr][x][y+1] == inf:
      heapq.heappush(now,[pt+1,dr,x,y+1])
  if dr == 3:
    for dr2 in range(4):
      if dijk[dr2][x][y] == inf:
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
  
  #print(now)
else:
  print(-1)
'''
for x in dijk:
  print('##')
  for y in x:
    print(y)
'''

Fixed submission:
#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[inf for _ in range(w)] for _ in range(h)]
seen[x1][y1] = 0
from heapq import heappush as push
from heapq import heappop as pop
now = [[0,x1,y1]]

while now:
  s,x,y = pop(now)
  if x == x2 and y == y2:
    print(s)
    exit()
  for i in range(1,k+1):
    if x-i == -1 or raw[x-i][y] == '@' or seen[x-i][y] < s+1:
      break
    if seen[x-i][y] != s+1:
      seen[x-i][y] = s+1
      push(now,[s+1,x-i,y])
  for i in range(1,k+1):
    if y-i == -1 or raw[x][y-i] == '@' or seen[x][y-i] < s+1:
      break
    if seen[x][y-i] != s+1:
      seen[x][y-i] = s+1
      push(now,[s+1,x,y-i])
  for i in range(1,k+1):
    if x+i == h or raw[x+i][y] == '@' or seen[x+i][y] < s+1:
      break
    if seen[x+i][y] != s+1:
      seen[x+i][y] = s+1
      push(now,[s+1,x+i,y])
  for i in range(1,k+1):
    if y+i == w or raw[x][y+i] == '@' or seen[x][y+i] < s+1:
      break
    if seen[x][y+i] != s+1:
      seen[x][y+i] = s+1
      push(now,[s+1,x,y+i])
print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
#解説解答
#23:17
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(int,input().split())
x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
a = []
for _ in range(h):
  a.append(input())
inf = 10**10
dijk = [[[inf for _ in range(w)] for _ in range(h)] for _ in range(4)]
import heapq
now = [[0,0,x1,y1]]
# 0up 1down 2right 3left
while now:
  pt,dr,x,y = heapq.heappop(now)
  if x == x2 and y == y2:
    print((pt-1)//k+1)
    break
  if dijk[dr][x][y] != inf:
    continue
  dijk[dr][x][y] = pt
  
  if dr == 0 and x != 0:
    if a[x-1][y] == '.':
      heapq.heappush(now,[pt+1,dr,x-1,y])
  if dr == 0:
    for dr2 in range(4):
      if dr2 != dr:
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
        
  if dr == 1 and x != h-1:
    if a[x+1][y] == '.':
      heapq.heappush(now,[pt+1,dr,x+1,y])
  if dr == 1:
    for dr2 in range(4):
      if dr2 != dr:
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
        
  if dr == 2 and y != 0:
    if a[x][y-1] == '.':
      heapq.heappush(now,[pt+1,dr,x,y-1])
  if dr == 2:
    for dr2 in range(4):
      if dr2 != dr:
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
  
  if dr == 3 and y != w-1:
    if a[x][y+1] == '.':
      heapq.heappush(now,[pt+1,dr,x,y+1])
  if dr == 3:
    for dr2 in range(4):
      if dr2 != dr:
        heapq.heappush(now,[(pt-1)//k*k+k,dr2,x,y])
  
  #print(now)
else:
  print(-1)
'''
for x in dijk:
  print('##')
  for y in x:
    print(y)
'''

Fixed submission:
#16:41
h,w,k = map(int,input().split())
x1,y1,x2,y2 = map(lambda x:int(x)-1, input().split())
raw = []
for _ in range(h):
  raw.append(input())
inf = 10**6
seen = [[inf for _ in range(w)] for _ in range(h)]
seen[x1][y1] = 0
from heapq import heappush as push
from heapq import heappop as pop
now = [[0,x1,y1]]

while now:
  s,x,y = pop(now)
  if x == x2 and y == y2:
    print(s)
    exit()
  for i in range(1,k+1):
    if x-i == -1 or raw[x-i][y] == '@' or seen[x-i][y] < s+1:
      break
    if seen[x-i][y] != s+1:
      seen[x-i][y] = s+1
      push(now,[s+1,x-i,y])
  for i in range(1,k+1):
    if y-i == -1 or raw[x][y-i] == '@' or seen[x][y-i] < s+1:
      break
    if seen[x][y-i] != s+1:
      seen[x][y-i] = s+1
      push(now,[s+1,x,y-i])
  for i in range(1,k+1):
    if x+i == h or raw[x+i][y] == '@' or seen[x+i][y] < s+1:
      break
    if seen[x+i][y] != s+1:
      seen[x+i][y] = s+1
      push(now,[s+1,x+i,y])
  for i in range(1,k+1):
    if y+i == w or raw[x][y+i] == '@' or seen[x][y+i] < s+1:
      break
    if seen[x][y+i] != s+1:
      seen[x][y+i] = s+1
      push(now,[s+1,x,y+i])
print(-1)