LeetCode 2577. Minimum Time to Visit a Cell In a Grid in F#

URL

Minimum Time to Visit a Cell In a Grid - LeetCode

Code

https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/challenge/202411/minimum_time_to_visit_a_cell_in_a_grid/main.fsx

#r "nuget:FSharpx.Collections"

open FSharpx.Collections

let minimumTime (grid: int[,]) : int =
    let rows, cols = Array2D.length1 grid, Array2D.length2 grid
    let steps = [ (-1, 0); (0, -1); (1, 0); (0, 1) ]

    let isValid (r, c) =
        r >= 0 && r < rows && c >= 0 && c < cols

    let rec minimumTime' q (minTimes: int[,]) =
        match PriorityQueue.tryPop q with
        | None -> -1
        | Some((time, r, c), q) ->
            if r = rows - 1 && c = cols - 1 then
                time
            else
                let nexts = steps |> List.map (fun (x, y) -> r + x, y + c) |> List.filter isValid

                let q =
                    nexts
                    |> List.fold
                        (fun acc (r, c) ->
                            let wait = if (grid.[r, c] - time) % 2 = 0 then 1 else 0
                            let nextTime = max (time + 1) (grid.[r, c] + wait)

                            if nextTime < minTimes.[r, c] then
                                minTimes.[r, c] <- nextTime
                                PriorityQueue.insert (nextTime, r, c) acc
                            else
                                acc)
                        q

                minimumTime' q minTimes

    if grid.[0, 1] > 1 && grid.[1, 0] > 1 then
        -1
    else
        let q = PriorityQueue.empty false |> PriorityQueue.insert (0, 0, 0)
        let minTimes = Array2D.init rows cols (fun _ _ -> System.Int32.MaxValue)
        minimumTime' q minTimes