Shohei Yoshida
Shohei Yoshida's Blog

Shohei Yoshida's Blog

LeetCode 1926. Nearest Exit from Entrance in Maze in F#

Shohei Yoshida's photo
Shohei Yoshida
·Nov 21, 2022·

1 min read

URL

leetcode.com/problems/nearest-exit-from-ent..

Code

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

let nearestExit (maze: char [,]) ((row, col): int * int) : int =
    let rows = Array2D.length1 maze
    let cols = Array2D.length2 maze

    let rec nearestExit' (q: (int * int * int) list) (maze: char [,]) =
        match q with
        | [] -> -1
        | _ ->
            let rev = List.rev q
            let (row, col, step) = rev |> List.head

            if row < 0 || row >= rows || col < 0 || col >= cols then
                if step = 1 then
                    nearestExit' (List.tail rev) maze
                else
                    step - 1
            else
                let steps = [ (-1, 0); (0, -1); (1, 0); (0, 1) ]

                let q' =
                    steps
                    |> List.fold
                        (fun acc (x, y) ->
                            let newX, newY = row + x, col + y

                            if newX < 0
                               || newX >= rows
                               || newY < 0
                               || newY >= cols then
                                (newX, newY, step + 1) :: acc
                            elif newX >= 0
                                 && newX < rows
                                 && newY >= 0
                                 && newY <= cols
                                 && maze.[newX, newY] = '.' then
                                maze.[newX, newY] <- '+'
                                (newX, newY, step + 1) :: acc
                            else
                                acc)
                        (rev |> List.tail)

                nearestExit' q' maze

    maze.[row, col] <- '+'
    nearestExit' [ (row, col, 0) ] maze
 
Share this