module Weighted01DirectedGraph
  (* 道の表現 *)
  (Path : sig
    type t
    (* 辺の名前 *)
    type edge
    (* 長さ0の道 *)
    val nil : t
    (* 道の後ろに辺を付け足した道 *)
    val snoc : t -> edge -> t
  end) :
sig
  val bfs01 :
    (* 頂点数 *)
    int ->
    (* 辺の名前が付いた隣接リスト *)
    (* 辺の重さが0ならfalse，1ならtrue *)
    ('v -> ('v * Path.edge * bool) list) ->
    (* 始点 *)
    'v ->
    (* 最短経路を返す関数 辿り着けなければNoneを返す） *)
    ('v -> Path.t option)
end =
struct
  let bfs01 n es s =
    (* 始点sからの経路 *)
    let d = Hashtbl.create n in
    (* 現在BFSで走査している頂点のリスト *)
    let vps = ref [(s, Path.nil)] in
    let rec bfs t =
      match Hashtbl.find_opt d t, !vps with
      (* もう既に全ての頂点までの経路が分かっている *)
      | None, [] -> None
      (* 既に終点までの経路が分かっているので返す *)
      | Some _ as ans, _ -> ans
      (* 終点までの経路が分かっていないので，01BFSを続行 *)
      | None, _ :: _ -> vps := List.fold_left dfs [] !vps; bfs t
    (* 重さ0の辺をDFSで縮約 *)
    and dfs vps (v, p) =
      if Hashtbl.mem d v then vps
      else begin
        Hashtbl.add d v p;
        List.fold_left (fun vps (u, e, b) ->
          if b
          then (u, Path.snoc p e) :: vps
          else dfs vps (u, Path.snoc p e)) vps (es v)
      end
    in bfs
end

module G = Weighted01DirectedGraph
(struct
  type t = int
  type edge = int
  let nil = 0
  let snoc = ( + )
end)

type dir = Neutral | Left | Right | Up | Down

let () = Scanf.scanf "%d %d %d\n%d %d %d %d\n" @@ fun h w k x1 y1 x2 y2 ->
  let x1 = x1 - 1 in
  let x2 = x2 - 1 in
  let y1 = y1 - 1 in
  let y2 = y2 - 1 in
  let css = Array.init h @@ fun _ -> Scanf.scanf "%s\n" Fun.id in
  let d = G.bfs01 (h * w * 40) (fun (i, j, s, dir) ->
    List.filter_map (fun (i, j, dir') ->
      if i < 0 || h <= i || j < 0 || w <= j || css.(i).[j] = '@'
      then None
      else if (dir = Neutral || dir = dir') && s < k
      then Some ((i, j, s + 1, dir'), 0, false)
      else Some ((i, j, 1, dir'), 1, true))
    [(i - 1, j, Up); (i + 1, j, Down); (i, j - 1, Left); (i, j + 1, Right)])
    (x1, y1, 0, Neutral) in
  Printf.printf "%d\n" @@
  max (-1) @@
  succ @@
  Array.fold_left (List.fold_left min) max_int @@
  Array.init k @@ fun s ->
    let s = s + 1 in
    List.map (fun o -> Option.value ~default:max_int o)
    [ d (x2, y2, s, Left); d (x2, y2, s, Right); d (x2, y2, s, Up); d (x2, y2, s, Down) ]

