Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

2013-03-06から1日間の記事一覧

JOI 春合宿 2012-day3 Sokoban

問題文 : 倉庫番解法 : 「倉庫番の逆」を考える. すなわち, 目標地点から箱を引っ張りまわすBFS を考える. 箱の置き方がO(MN) 個, 隣接する頂点がたかだか4 個であるため, 状態数はO(MN) である.各状態に遷移したら, 答えには連結成分の大きさを足してやれば…