結果

問題 No.424 立体迷路
ユーザー ichibanshiboriichibanshibori
提出日時 2016-09-24 07:31:43
言語 OCaml
(5.1.0)
結果
AC  
実行時間 42 ms / 2,000 ms
コード長 2,923 bytes
コンパイル時間 223 ms
コンパイル使用メモリ 20,992 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-17 08:33:57
合計ジャッジ時間 1,003 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

open Str

module ISet = Set.Make(
    struct
        let compare = compare
        type t = int * int
    end)

let () =
    let ( @! ) lst n = List.nth lst n
    and ( @> ) arr (i ,j) = arr.(i - 1).(j - 1)
    in
    let h, w = read_line () |>
        Str.split (regexp_string " ") |>
        fun lst -> (int_of_string (lst @! 0), int_of_string (lst @! 1))
    and sx, sy, gx, gy = read_line () |>
        Str.split (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 gx, gy, sx, sy = sx, sy, gx, gy in
    let mapArr = Array.make_matrix w h 0 in
    let readB (x, (line:string)) =
        for y = 1 to w do
            mapArr.(y - 1).(x - 1) <- int_of_char line.[y - 1] - int_of_char '0'
        done
    in
    for x = 1 to h do
        readB (x, read_line ())
    done;
    let searchPath sy sx =
        let dxy = [(1, 0); (0, 1); (-1, 0); (0, -1)] in
        
        let canMove1 (cy, cx) (dy, dx) =
            let y, x = cy + dy, cx + dx in
            
            (*Printf.printf "!%d, %d\n" y x;*)
            y >= 1 && y <= w && x >= 1 && x <= h &&
            abs((mapArr @> (y, x)) - (mapArr @> (cy, cx))) <= 1
            
        and canMove2 (cy, cx) (dy, dx) = 
            let y1, y2 = cy + dy, cy + dy * 2
            and x1, x2 = cx + dx, cx + dx * 2
            in
            y2 >= 1 && y2 <= w && x2 >= 1 && x2 <= h &&
            mapArr @> (cy, cx) = mapArr @> (y2, x2) &&
            mapArr @> (cy, cx) > mapArr @> (y1, x1)
        in
        let rec searchPath' lst chkedSet =
            match lst with
            | [] -> false
            |  pos::rest ->
                    let cy, cx = pos in

                    (*Printf.printf "%d %d\n" cy cx;*)
                    
                    let cand1 = List.filter (canMove1 (cy, cx)) dxy
                    and cand2 = List.filter (canMove2 (cy, cx)) dxy |>
                        List.map (fun (dy, dx) -> (dy * 2, dx * 2))
                    in
                    let cand = List.append cand1 cand2 in
                    let candLst = List.map (fun (dy, dx) -> (cy + dy, cx + dx)) cand in
                    
                    (*candLst |> List.iter (fun (y, x) -> Printf.printf "%d, %d\n" y x);*)
                    
                    if List.exists (fun (y, x) -> y = gy && x = gx) candLst then true
                    else
                        let nextLst = List.append candLst rest |>
                            List.filter (fun pos -> not (ISet.mem pos chkedSet))
                        and nextChkedSet = ISet.add (cy, cx) chkedSet
                        in
                        searchPath' nextLst nextChkedSet
        in
        if sy = gy && sx = gx then true
        else searchPath' [(sy, sx)] ISet.empty
    in
    searchPath sy sx |> (function | true -> "YES" | false -> "NO") |> print_endline
0