# LeetCode 1631. Path With Minimum Effort in F#

·

## URL

https://leetcode.com/problems/path-with-minimum-effort/?envType=daily-question&envId=2023-09-16

## Code

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

``````#r "nuget:FSharpx.Collections"

open System
open FSharpx.Collections

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

let rec minimumEffortPath' (q: IPriorityQueue<(int * int * int)>) (dp: int[,]) =
match PriorityQueue.tryPop q with
| None -> dp.[rows - 1, cols - 1]
| Some((maxDiff, row, col), q') ->
let q'' =
steps
|> List.map (fun (x, y) -> row + x, col + y)
|> List.filter (fun (x, y) -> x >= 0 && x < rows && y >= 0 && y < cols)
|> List.fold
(fun acc (x, y) ->
let diff = Math.Abs(heights.[row, col] - heights.[x, y])
let maxDiff' = Math.Max(diff, maxDiff)

if maxDiff' < dp.[x, y] then
dp.[x, y] <- maxDiff'
PriorityQueue.insert (maxDiff', x, y) acc
else
acc)
q'

minimumEffortPath' q'' dp

let dp = Array2D.init rows cols (fun _ _ -> Int32.MaxValue)
dp.[0, 0] <- 0

let q = PriorityQueue.empty false |> PriorityQueue.insert (0, 0, 0)
minimumEffortPath' q dp
``````