きままにものづくり

日々の気付いたことなんかを書いてます。

SRM625Div1Medium

問題

サイズNの平面を考える。スタート点'b'と穴'H'とゴール'$'と通常のパネル'.'が存在する。'b'は複数存在し、その上には駒が置いてある。駒は上下左右に3マスずつ移動可能である。駒の移動先、もしくは移動する間の2つのマスが'H'ならそのマスへは移動できない。駒を'H'に到達させないようにするために必要な最小の'H'の追加数を求めよ。

解法

この問題は最小カット問題へと帰着できる。スタート点が複数あるが、sourceとsinkを別に作り無限のcapacityを持つエッジで結ぶことで解くことができる。答えである流量Fは最大でも8である。また、エッジの数は頂点の数の2上に比例する。頂点の数はN/3となる。

計算量

O(FN^2)
F:流量
N:平面のサイズ

コード