083 A - Darker and Darker

参考

解説

破壊的な実装

公式解説通りに実装します. 今回のポイントは破壊的・非関数型的な実装です. F#には独自のキュー(関数型のキュー)がなく, .NETの破壊的なキューしかありません. 関数型のキューを自前実装するのも面倒です. 余程の強烈なこだわりでもない限り素直に.NET実装を使えばいいでしょう.

念のため書いておくと, いわゆる関数型言語でも効率が必要な場合は破壊的な実装を使います. 関数の内部など影響範囲が確実に限定されていれば問題はなく, それを突き詰めて関数とアクションの分離にまで持ち上げたのがHaskellです. AtCoderでHaskellの実装を見るとシンプルな実装はしづらいようです.

さらについでに書いておくと, 少なくともAtCoder上のOCaml勢は破壊的な実装を厭いません. 困ったらOCaml勢の実装も参考にしましょう. 今回も解説用のコードはOCamlを参考にしました.

入出力

入出力とその変数は次のようにします.

1
2
3
4
5
let solve H W Aa = "これから実装"

let H,W = stdin.ReadLine().Split() |> Array.map int |> (fun x -> x.[0],x.[1])
let Aa = Array.init H (fun _ -> stdin.ReadLine())
solve H W Aa |> stdout.WriteLine

変数の初期化

まずはキューを初期化しつつ, フラグ管理・操作回数管理用の配列を作ります. F#では配列の配列ではなく二次元の配列があり, 今回は二次元の配列が便利そうなのでこちらを使います.

1
2
3
  let q = System.Collections.Generic.Queue<int*int>()
  let Da = Array2D.init H W (fun _ _ -> -1)
  Aa |> array2D |> Array2D.iteri (fun i j c -> if c='#' then Da.[j,i] <- 0; q.Enqueue(j,i))

Daが本体のループでゴリゴリ書き換える変数です. そもそもとしてF#の配列は破壊的なデータ型で, mutableをつけなくてもDa.[j,i] <- 0で破壊的に変更できます. Daは.を-1, #を0で初期化しています. 最終的に何回目の処置で黒に変わったかを表す二次元配列で, -1はまだ書き換えできていない状態を表します.

さらに#の場所もキューに積みます. ここでAaのi,jはそれぞれy座標とx座標で混乱するため, 上記のDaとqは添字を入れ変えてx,yと書けるようにしています.

本体のループ処理

let mutable ans = 0で最終的に返す変数を宣言します. あとは適宜qに積みつつqが尽きるまでループします. qに値があるかどうかはプロパティq.Countで判定できます.

1
2
3
4
  let mutable ans = 0
  while q.Count <> 0 do
    "いろいろな処理"
  ans

いろいろな処理の部分を考えます. 何はともあれqから値をポップします.

1
    let x0,y0 = q.Dequeue()

.NETではq.Dequeue()です. ポップした値を中心にして周囲4マスの値を確認します. 周囲4マス分の移動を表す配列Maを用意します.

1
  let Ma = [|(-1,0);(0,-1);(1,0);(0,1)|]

さらに配列の範囲外参照と訪問状態をチェックする関数を準備します.

1
  let isWhite x y (Da:int[,]) = 0<=y && y<H && 0<=x && x<W && Da.[x,y]=(-1)

ここで白(.)かどうかの判定は初期値ではなく書き換えたかどうかを判定したいため, 入力のAaではなくDaの値で判定します. 一緒に配列の範囲内か確認するべく値Da.[x,y]ではなく配列自体を渡しています.

この二つを使って次のように周辺4マスの状態を確認しつつ値を更新します.

1
2
3
4
    let x0,y0 = q.Dequeue()
    Ma |> Array.iter (fun (dx,dy) ->
      let x,y = x0+dx, y0+dy
      if isWhite x y Da then ans <- Da.[x0,y0]+1; Da.[x,y] <- ans; q.Enqueue(x,y))

Maの各値をArray.iterで参照します. 周囲4マスのどれかを表すx,yを準備してx,yの値が白(.)かどうかを判定します. 点x,yがまだ白ならDa.[x0,y0]+1でDa.[x,y]を更新します. 最後に新たに黒(#)にしたフラグ立てとしてq.Enqueue(x,y)でキューにx,yを積みます.

途中ansをバリバリ書き換えているためこれで最終的な解答になるか微妙な不安がありますが, 都度キューに積んだ値を見てループしているため, これで常に最新の変更回数が取れています.