let id x = x

let () =
  let solve h w k =
    let calc_score (i,j) =
      List.fold_left min i [h-1-i; j; w-1-j]
    in
    let calc_ans score =
      (score + k - 1) / k + 1
    in
    let delta = [0,1; 1,0; 0,-1; -1,0] in
    let a = Array.init h (fun _ -> Scanf.scanf "%s " id) in
    let rec loop i j =
      if j = w then loop (i+1) 0
      else if a.(i).[j] = 'S' then i,j
      else loop i (j+1)
    in
    let start = loop 0 0 in
    let q = Queue.create () in
    Queue.add (start, 0) q;
    let ans = ref (calc_ans (calc_score start)) in
    let rec bfs () =
      if Queue.is_empty q then !ans
      else
        let (i,j), k' = Queue.pop q in
        let score = calc_score (i,j) in
        ans := min !ans (calc_ans score);
        if score = 0 then !ans else
        if k' = k then bfs () else (
          delta
          |> List.iter (fun (dx, dy) ->
            let x, y = i+dx, j+dy in
            if a.(x).[y] = '.' then (
              a.(x).[y] <- '#';
              Queue.add ((x,y),k'+1) q
            )
          );
          bfs ()
        )
    in
    bfs ()
  in
  Scanf.scanf "%d %d %d " solve
  |> Printf.printf "%d\n"
