URL

https://leetcode.com/problems/unique-paths-ii/description/

Code

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

let uniquePathsWithObstacles (obstacleGrid: int[,]) : int =
    let rows, cols = Array2D.length1 obstacleGrid, Array2D.length2 obstacleGrid
    let steps = [ (1, 0); (0, 1) ]

    let rec uniquePathsWithObstacles' q (dp: int[,]) =
        if Set.isEmpty q then
            dp.[rows - 1, cols - 1]
        else
            let q' =
                q
                |> Seq.fold
                    (fun acc (r, c) ->
                        steps
                        |> List.map (fun (x, y) -> r + x, c + y)
                        |> List.filter (fun (x, y) -> x < rows && y < cols && obstacleGrid.[x, y] = 0)
                        |> List.fold
                            (fun acc' (x, y) ->
                                dp.[x, y] <- dp.[x, y] + dp.[r, c]
                                Set.add (x, y) acc')
                            acc)
                    Set.empty

            uniquePathsWithObstacles' q' dp

    if obstacleGrid.[0, 0] = 0 then
        let q = Set.empty |> Set.add (0, 0)
        let dp = Array2D.zeroCreate rows cols
        dp.[0, 0] <- 1
        uniquePathsWithObstacles' q dp
    else
        0