結果

問題 No.424 立体迷路
ユーザー ichibanshiboriichibanshibori
提出日時 2016-10-15 16:51:10
言語 OCaml
(5.1.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,401 bytes
コンパイル時間 182 ms
コンパイル使用メモリ 20,480 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-17 08:34:41
合計ジャッジ時間 986 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 1 ms
6,944 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 1 ms
6,944 KB
testcase_16 AC 1 ms
6,944 KB
testcase_17 AC 1 ms
6,944 KB
testcase_18 AC 1 ms
6,940 KB
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 1 ms
6,940 KB
testcase_21 AC 1 ms
6,940 KB
testcase_22 AC 2 ms
6,940 KB
testcase_23 AC 1 ms
6,944 KB
testcase_24 AC 3 ms
6,940 KB
testcase_25 AC 3 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

let ( @! ) = List.nth
let ( @> ) arr (i ,j) = arr.(i - 1).(j - 1)

let choose f lst =
  let rec choose' f lst result =
    match lst with
    | [] -> result
    | x::xs ->
      let nextResult =
        match f x with
        | Some v -> v::result
        | None -> result
      in
      choose' f xs nextResult
  in
  choose' f lst []

let searchPath mapArr (w, h) (sy, sx) (gy, gx) =
  let chkArr = Array.make_matrix w h false
  and dxy = [(1, 0); (0, 1); (-1, 0); (0, -1)]
  in
  let canMove1 (cy, cx) (dy, dx) =
    let y, x = cy + dy, cx + dx in

    if y >= 1 && y <= w && x >= 1 && x <= h &&
       abs((mapArr @> (y, x)) - (mapArr @> (cy, cx))) <= 1 &&
       not (chkArr @> (y, x))
    then Some (y, x)
    else None

    and canMove2 (cy, cx) (dy, dx) =
      let y1, y2 = cy + dy, cy + dy * 2
      and x1, x2 = cx + dx, cx + dx * 2
      in
      if y2 >= 1 && y2 <= w && x2 >= 1 && x2 <= h &&
         mapArr @> (cy, cx) = mapArr @> (y2, x2) &&
         mapArr @> (cy, cx) > mapArr @> (y1, x1) &&
         not (chkArr @> (y2, x2))
      then Some (y2, x2)
      else None
  in
  let rec searchPath' lst =
    match lst with
    | [] -> false
    | pos::rest ->
      let cy, cx = pos in

      if cy = gy && cx = gx then true
      else (
        let cand1 = choose (canMove1 (cy, cx)) dxy
        and cand2 = choose (canMove2 (cy, cx)) dxy
        in
        let candLst = cand1 @ cand2 in
        let nextLst = candLst @ rest in
        List.iter (fun (y, x) -> chkArr.(y - 1).(x - 1) <- true) candLst;
        searchPath' nextLst
      )
  in
  searchPath' [(sy, sx)]

let () =
  let h, w = read_line () |>
             Str.split (Str.regexp_string " ") |>
             fun lst -> (int_of_string (lst @! 0), int_of_string (lst @! 1))
  and sx, sy, gx, gy = read_line () |>
                       Str.split (Str.regexp_string " ") |>
                       fun lst -> (int_of_string (lst @! 0), int_of_string (lst @! 1),
                                   int_of_string (lst @! 2), int_of_string (lst @! 3))
  in
  let mapArr = Array.make_matrix w h 0 in
  let rec readB x =
    if x < h then (
      let  line = read_line () in
      String.iteri
        (fun y c -> mapArr.(y).(x) <- int_of_char c - int_of_char '0')
        line;
      readB (x + 1)
    )
  in
  readB 0;
  searchPath mapArr (w, h) (sy, sx) (gy, gx) |>
  (function | true -> "YES" | false -> "NO") |>
  print_endline
0