output_description: Print the minimum number of strokes Snuke takes to travel from the square
  (x_1,y_1) to (x_2,y_2), or print `-1` if the travel is impossible.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      H W K
      x_1 y_1 x_2 y_2
      c_{1,1}c_{1,2} .. c_{1,W}
      c_{2,1}c_{2,2} .. c_{2,W}
      :
      c_{H,1}c_{H,2} .. c_{H,W}
attempt: # -*- coding: utf-8 -*-
  
  H, W, K = map(int, input().split())
  x1, y1, x2, y2 = map(int, input().split())
  
  C = []
  for _ in range(H):
      C.append(input())
  
  count_matrix = [[float("inf") for _ in range(W)] for _ in range(H)]
  
  
  def calc(count, pos, to_dir, move_count):
      if count_matrix[pos["x"]][pos["y"]] <= count:
          return
  
      count_matrix[pos["x"]][pos["y"]] = count
  
      if to_dir == "N" or to_dir == "S":
          if to_dir == "N" and can_move(to_n(pos)):
              if move_count == K:
                  count += 1
                  move_count = 0
              calc(count, to_n(pos), "N", move_count + 1)
          if to_dir == "S" and can_move(to_s(pos)):
              if move_count == K:
                  count += 1
                  move_count = 0
              calc(count, to_s(pos), "S", move_count + 1)
          if can_move(to_w(pos)):
              calc(count + 1, to_w(pos), "W", 1)
          if can_move(to_e(pos)):
              calc(count + 1, to_e(pos), "E", 1)
  
      if to_dir == "W" or to_dir == "E":
          if to_dir == "W" and can_move(to_w(pos)):
              if move_count == K:
                  count += 1
                  move_count = 0
              calc(count, to_w(pos), "W", move_count + 1)
          if to_dir == "E" and can_move(to_e(pos)):
              if move_count == K:
                  count += 1
                  move_count = 0
              calc(count, to_e(pos), "E", move_count + 1)
          if can_move(to_n(pos)):
              calc(count + 1, to_n(pos), "N", 1)
          if can_move(to_s(pos)):
              calc(count + 1, to_s(pos), "S", 1)
  
      return
  
  
  def can_move(pos):
      return (
          0 <= pos["x"] <= H - 1
          and 0 <= pos["y"] <= W - 1
          and C[pos["x"]][pos["y"]] != "@"
      )
  
  
  def to_n(pos):
      return {"x": pos["x"] - 1, "y": pos["y"]}
  
  
  def to_s(pos):
      return {"x": pos["x"] + 1, "y": pos["y"]}
  
  
  def to_w(pos):
      return {"x": pos["x"], "y": pos["y"] - 1}
  
  
  def to_e(pos):
      return {"x": pos["x"], "y": pos["y"] + 1}
  
  
  px = x2 - 1
  py = y2 - 1
  
  dest_pos = {"x": px, "y": py}
  
  if can_move(to_n(dest_pos)):
      calc(1, to_n(dest_pos), "N", 1)
  
  if can_move(to_s(dest_pos)):
      calc(1, to_s(dest_pos), "S", 1)
  
  if can_move(to_w(dest_pos)):
      calc(1, to_w(dest_pos), "W", 1)
  
  if can_move(to_e(dest_pos)):
      calc(1, to_e(dest_pos), "E", 1)
  
  ans = count_matrix[x1 - 1][y1 - 1]
  
  print(ans if ans != float("inf") else -1)
  
problem_description: Statement
  
  Snuke, a water strider, lives in a rectangular pond that can be seen as a grid
  with H east-west rows and W north-south columns. Let (i,j) be the square at
  the i-th row from the north and j-th column from the west.
  
  Some of the squares have a lotus leaf on it and cannot be entered. The square
  (i,j) has a lotus leaf on it if c_{ij} is `@`, and it does not if c_{ij} is
  `.`.
  
  In one stroke, Snuke can move between 1 and K squares (inclusive) toward one
  of the four directions: north, east, south, and west. The move may not pass
  through a square with a lotus leaf. Moving to such a square or out of the pond
  is also forbidden.
  
  Find the minimum number of strokes Snuke takes to travel from the square
  (x_1,y_1) to (x_2,y_2). If the travel from (x_1,y_1) to (x_2,y_2) is
  impossible, point out that fact.
samples: [{"input": "3 5 2\n    3 2 3 4\n    .....\n    .@..@\n    ..@..", "output": "5\n    \n\nInitially, Snuke is at the square (3,2). He can reach the square (3, 4) by\nmaking five strokes as follows:\n\n  * From (3, 2), go west one square to (3, 1).\n\n  * From (3, 1), go north two squares to (1, 1).\n\n  * From (1, 1), go east two squares to (1, 3).\n\n  * From (1, 3), go east one square to (1, 4).\n\n  * From (1, 4), go south two squares to (3, 4).\n\n* * *"}, {"input": "1 6 4\n    1 1 1 6\n    ......", "output": "2\n    \n\n* * *"}, {"input": "3 3 1\n    2 1 2 3\n    .@.\n    .@.\n    .@.", "output": "-1"}]