【AtCoder】【F#】abc007_3 幅優先探索

C: 幅優先探索 - AtCoder Beginner Contest 007 | AtCoder

F#と幅優先探索を同時に学ぼうとした。

namespace App

open System.Collections.Generic

module Main =
    let createGraph (maze : string [] []) : Dictionary<int * int, (int * int) list> =
        let graph = new Dictionary<int * int, (int * int) list>()
        let mutable count1 = 0
        for item1 in maze do
            let mutable count2 = 0
            for _item2 in item1 do
                let mutable arr : (int * int) list = []
                if count1 < maze.Length - 1 && maze.[count1 + 1].[count2] = "." then
                    arr <- (count1 + 1, count2) :: arr
                if count2 < item1.Length - 1 && maze.[count1].[count2 + 1] = "." then
                    arr <- (count1, count2 + 1) :: arr
                if count1 > 0 && maze.[count1 - 1].[count2] = "." then
                    arr <- (count1 - 1, count2) :: arr
                if count2 > 0 && maze.[count1].[count2 - 1] = "." then
                    arr <- (count1, count2 - 1) :: arr
                graph.Add((count1, count2), arr)
                count2 <- count2 + 1
            count1 <- count1 + 1
        graph

    let procedure (maze : string [] []) (start : int * int) (goal : int * int) : int =
        let queue = new Queue<int * int>()
        let graph = createGraph maze
        let mutable checkedList = []
        queue.Enqueue(start)
        let mutable breakFlg = false
        let dict = Dictionary<(int * int), ((int * int) * int)>()
        dict.Add(start, ((-1, -1), 0))
        while not breakFlg && queue.Count > 0 do
            let target = queue.Dequeue()
            if not (List.contains target checkedList) then
                if target = goal then
                    breakFlg <- true
                for item in graph.[target] do
                    queue.Enqueue(item)
                    let tryGetResult = dict.TryGetValue(item)
                    if not (fst tryGetResult) then
                        dict.Add(item, (target, snd dict.[target] + 1))
                checkedList <- target :: checkedList
        snd dict.[goal]

    [<EntryPoint>]
    let main _argv : int =
        let inputNums1 =
            stdin.ReadLine().Split(' ')
            |> Array.map int
            |> Array.toList

        let R = inputNums1.Head
        let inputNums2 = stdin.ReadLine().Split(' ') |> Array.map int
        let start = (inputNums2.[0] - 1, inputNums2.[1] - 1)
        let inputNums3 = stdin.ReadLine().Split(' ') |> Array.map int
        let goal = (inputNums3.[0] - 1, inputNums3.[1] - 1)

        let rec readMaze (count : int) (maze : string [] []) =
            match count with
            | 0 -> maze
            | _ ->
                Array.append maze
                    [| (stdin.ReadLine().ToCharArray() |> Array.map string) |]
                |> readMaze (count - 1)

        let maze = readMaze R [||]
        procedure maze start goal |> printfn "%d"
        0

かなり手続き型に逃げてしまってF#つかってる意味あるのか……？という感じ。

徐々に慣れていきたい。

グラフ

let graph = createGraph maze

ここでいうグラフとは、それぞれの座標をキー、隣接した座標のリストをバリューとしたDictionary型の変数。

まずは入力値からこれを拵える。

キュー・確認済みリスト・親と何歩目かの記録リスト

// キュー
 let queue = new Queue<int * int>()
queue.Enqueue(start)
// 確認済リスト
 let mutable checkedList = []
// 親と何歩目かの記録リスト
let dict = Dictionary<(int * int), ((int * int) * int)>() // (<座標>, (親の座標, 現在の歩数))
dict.Add(start, ((-1, -1), 0))

キュー

キューにグラフから取得した座標を入れていく。

幅優先探索でキューを使う理由はスタート地点から近い順に確認したいから。

確認済リスト

確認済の座標は配列に入れて記録する。

下の記事のGIFを例にするとわかりやすいと思う。

qiita.com

https://camo.qiitausercontent.com/3baf2198a91031a9e11956a630b3baf337e97a15/68747470733a2f2f71696974612d696d6167652d73746f72652e73332e616d617a6f6e6177732e636f6d2f302f37373731362f63326265643663622d663261382d653839352d323933312d6338616536653563396233322e676966

このGIFでいうと塗りつぶした座標は二度とチェックしない。

なので塗りつぶし済座標は配列に入れて確認時に参照する。

親と何歩目かの記録リスト

ゴールに到達するだけなら必須ではないが、問題としては最短経路の歩数を求める必要がある。

DIctionary型の変数を作り、対象の座標をキーとして、その座標の親となる座標とその座標到達時点の歩数を記録するようにする。

歩数は親の歩数に+1して記録する。

参考

これがかなりわかりやすかった。

www.amazon.co.jp