let (n1, n2) = (3, 9)

let n_limit = 100
let mdt = Array.make_matrix n2 n2 0
let path = Array.make n_limit 0
let dx = [| 0; -1; 0; 1 |]
let dy = [| 1; 0; -1; 0 |]
let dir = [| "r"; "u"; "l"; "d" |]

type puzzle = { f : int array; space : int; md : int }

let initialize_mdt () =
  for i = 0 to n2 - 1 do
    for j = 0 to n2 - 1 do
      mdt.(i).(j) <- abs (i / n1 - j / n1) + abs (i mod n1 - j mod n1)
    done
  done

let get_all_md f =
  Array.fold_left (fun (i, sum) e ->
    (i + 1, if e = n2 then sum else sum + mdt.(i).(e-1)))
    (0, 0) f
  |> snd

let dfs pzl limit =
  let rec doit depth prev pzl =
    if pzl.md = 0 then true
    else if depth + pzl.md > limit then false
    else begin
      let sx = pzl.space / n1 in
      let sy = pzl.space mod n1 in
      let rec move r =
        if r = 4 then false
        else begin
          let tx = sx + dx.(r) in
          let ty = sy + dy.(r) in
          if tx < 0 || ty < 0 || tx >= n1 || ty >= n1 then move (r + 1)
          else if max prev r - min prev r = 2 then move (r + 1)
          else begin
            let { f; space; md } = pzl in
            let a = tx*n1 + ty in
            let b = sx*n1 + sy in
            let md = md - mdt.(a).(f.(a) - 1) in
            let md = md + mdt.(b).(f.(a) - 1) in
            let t = f.(a) in
            f.(a) <- f.(b);
            f.(b) <- t;
            if doit (depth + 1) r { f; space = a; md } then begin
              path.(depth) <- r;
              true
            end else move (r + 1)
          end
        end in
      move 0
    end in
  doit 0 (-n_limit) pzl

let idastar f space =
  let pzl = { f; space; md = get_all_md f } in
  let rec doit limit =
    if limit > n_limit then assert false
    else if dfs pzl limit then begin
      let str = ref "" in
      for i = 0 to limit - 1 do
        str := !str ^ dir.(path.(i));
      done;
      !str
    end else doit (limit + 1) in
  doit pzl.md

let () =
  initialize_mdt ();
  let f = Array.make n2 0 in
  let space = ref 0 in
  for i = 0 to n2 - 1 do
    f.(i) <- Scanf.scanf "%d " (fun i -> i);
    if f.(i) = 0 then begin
      f.(i) <- n2;
      space := i;
    end
  done;
  idastar f !space |> String.length |> Printf.printf "%d\n"