AGC014 Closed Rooms
所感
700 初自力、ものすごい逆詐称だ
problemsのれこめんどというのを使ってみたけど、500埋め終わったらこれをやったらいいかな
問題概要
'.'と'#' からなる盤面H*Wのが与えられる。1回の操作でイカができる時、最短何回で外周(0行目、0列目、H-1行目、W-1列目)に到達できるかを求めよ。
- 今いるマスから隣り合う部屋に移動することを K回まで繰り返す。ただし、'#'には移動することはできない - その後、'#'を K 個まで選び、それらを'.'に置き換える。
取った方針
Kマス移動してK個の壁を破壊できるので、壁は存在しないとみなすことができる。
最初の操作では壁を破壊することができないので、最初のKマスの移動だけ全探索して、行ける中で外周に一番近い点を見つけたあと、そこから壁がないものとして直進した時が最適となる。
全探索はBFSをして、その後に外周までの距離をKで割って切り上げたものが答え。
正しい方針
同上
得られた知見
・特になし
解くのに必要な要素
・Kマス移動 + K個壁破壊 -> 壁は無いものとして扱うことが可能
・BFS
周辺調査によって得られた知見
特になし
