LeetCode 1293. Shortest Path in a Grid with Obstacles Elimination in F#

Shohei Yoshida
·Oct 30, 2022·

1 min read

URL

leetcode.com/problems/shortest-path-in-a-gr..

Code

github.com/syohex/dotnet-study/blob/master/..

``````let shortestPath (grid: int [,]) (k: int) : int =
let rows = Array2D.length1 grid
let cols = Array2D.length2 grid
let moves = [ (1, 0); (0, 1); (-1, 0); (0, -1) ]

let rec shortestPath' (grid: int [,]) q visited =
match q with
| [] -> -1
| (row, col, eliminations, steps) :: t ->
if row = rows - 1 && col = cols - 1 then
steps
else
let newCandidates =
moves
|> List.map (fun (x, y) -> row + x, col + y)
|> List.filter (fun (x, y) -> x >= 0 && x < rows && y >= 0 && y < cols)
|> List.map (fun (x, y) -> x, y, eliminations - grid.[x, y])
|> List.filter (fun (x, y, e) -> e >= 0 && Set.contains (x, y, e) visited |> not)
|> List.map (fun (x, y, e) -> x, y, e, steps + 1)

let newVisited =
newCandidates
|> List.fold (fun acc (x, y, e, _) -> Set.add (x, y, e) acc) visited

let newQ = newCandidates @ t
shortestPath' grid newQ newVisited

shortestPath' grid [ (0, 0, k, 0) ] Set.empty
``````

Share this