水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

九州大学プログラミングコンテスト2018:C - Ito Campus

問題

beta.atcoder.jp

解法

「ゾンビ島」( JOI 2015/2016 予選 問題5 )にめちゃくちゃ似ている(というかほぼそのまま).

イノシシがいるマスから BFS で各マスのイノシシのいるマスまでの最短距離を調べる.ここで,最短距離が X 以下であるマスは壁にする.あとは,S から G へ BFS をすればよい.

解答

beta.atcoder.jp

1 RE + 7 WA.最初 DFS で頑張ろうとしてしまった.BFS を実装するも,ミスが多発した.

f:id:babcs2035:20181021212841p:plain