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: import collections
  
  H, W, K = [int(_) for _ in input().split()]
  x1, y1, x2, y2 = [int(_) - 1 for _ in input().split()]
  C = [[10**6 if s == "." else None for s in input()] for _ in range(H)]
  C[x1][y1] = 0
  Qx = collections.deque([(x1, y1)])  # 次にxが変化
  Qy = collections.deque([(x1, y1)])  # 次にyが変化
  while True:
      if not (Qx or Qy):
          break
      Qy2 = collections.deque([])
      while Qx:
          x, y = Qx.popleft()
          for nx in range(x + 1, H):
              if C[nx][y] is None:
                  break
              elif C[nx][y] == 10**6:
                  Qy2 += [(nx, y)]
                  C[nx][y] = C[x][y] + 1 + (nx - x - 1) // K
          for nx in range(x - 1, -1, -1):
              if C[nx][y] is None:
                  break
              elif C[nx][y] == 10**6:
                  Qy2 += [(nx, y)]
                  C[nx][y] = C[x][y] + 1 + (x - nx - 1) // K
      Qx2 = collections.deque([])
      while Qy:
          x, y = Qy.popleft()
          for ny in range(y + 1, W):
              if C[x][ny] is None:
                  break
              elif C[x][ny] == 10**6:
                  Qx2 += [(x, ny)]
                  C[x][ny] = C[x][y] + 1 + (ny - y - 1) // K
          for ny in range(y - 1, -1, -1):
              if C[x][ny] is None:
                  break
              elif C[x][ny] == 10**6:
                  Qx2 += [(x, ny)]
                  C[x][ny] = C[x][y] + 1 + (y - ny - 1) // K
      Qx = Qx2
      Qy = Qy2
  ans = C[x2][y2]
  print(ans if ans < 10**6 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"}]