Submission #52467430

---

Source Code Expand

let h, w, k = Scanf.scanf " %d %d %d" (fun i j k -> (i, j, k))
let s =
  Array.init h @@ fun _ ->
    Scanf.scanf " %s" Fun.id

let prefix_sum h w f =
  let a =
    Array.init h @@ fun _ ->
      Array.init (w + 1) @@ fun _ ->
        0 in
  for i = 0 to h - 1 do
    for j = 0 to w - 1 do
      a.(i).(j + 1) <- a.(i).(j) + (if f (i, j) = 'o' then 1 else 0)
    done
  done;
  a

let calc h w f =
  let s = prefix_sum h w f in
  let rec next p j = if j < w && not (p j) then next p (j + 1) else j in
  let rec calc_row (i, j) c =
    if j < w then begin
      let l = next (fun j -> f (i, j) <> 'x') j in
      let r = next (fun j -> f (i, j) = 'x') l in
      Iter.(l -- (r - 1))
      |> Iter.filter (fun j -> j + k <= r)
      |> Iter.map (fun j -> k - (s.(i).(j + k) - s.(i).(j)))
      |> Iter.iter c;
      calc_row (i, r) c
    end in
  Iter.(0 -- (h - 1))
  |> Iter.flat_map (fun i -> Iter.from_iter (calc_row (i, 0)))
  |> Iter.fold Int.min Int.max_int

let () =
  let t1 = calc h w (fun (i, j) -> s.(i).[j]) in
  let t2 = calc w h (fun (i, j) -> s.(j).[i]) in
  let t = Int.min t1 t2 in
  let t = if t < Int.max_int then t else -1 in
  Printf.printf "%d\n" t

Submission Info

Judge Result