LeetCode 1368. Minimum Cost to Make at Least One Valid Path in a Grid in F#

URL

https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/description/?envType=daily-question&envId=2025-01-18

Code

https://github.com/syohex/dotnet-study/blob/master/fsharp/leetcode/challenge/202501/minimum_cost_to_make_at_least_one_valid_path_in_a_grid/main.fsx

#r "nuget:FSharpx.Collections"

open FSharpx.Collections

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

    let rec minCost' q visited =
        match PriorityQueue.tryPop q with
        | None -> failwith "never reach here"
        | Some(((cost, row, col), q')) ->
            if row = rows - 1 && col = cols - 1 then
                cost
            elif Set.contains (row, col) visited then
                minCost' q' visited
            else
                let visited = Set.add (row, col) visited

                let q' =
                    steps
                    |> List.map (fun (x, y, s) -> row + x, col + y, s)
                    |> List.filter (fun (x, y, _) -> x >= 0 && x < rows && y >= 0 && y < cols)
                    |> List.fold
                        (fun acc (x, y, sign) ->
                            let cost' = cost + if grid.[row, col] = sign then 0 else 1
                            PriorityQueue.insert (cost', x, y) acc)
                        q'

                minCost' q' visited

    let q = PriorityQueue.empty false |> PriorityQueue.insert (0, 0, 0)
    minCost' q Set.empty