AOJ0588,Cheese

二つ目はBFS。

チーズ | Aizu Online Judge

AOJ0588,Cheese

解説

• チーズは常にひとつずつ硬くなる

作意。チーズの硬さにばらつきがあり、同じ硬さのものが散乱している状態をイメージすると難しく感じられるが、問題文や例をよく読むと、チーズの硬さはひとつずつしか増えず、また同じ硬さのものはひとつしかない。よって、硬さ1のチーズがゴール１、硬さ２のチーズがゴール２...といった調子で、チーズの数だけbfs最短経路問題を解けばよい。

• 経過時間の繰り越し

作意が理解できれば難しくない。ゴールひとつに到達するごとにスタートとゴールを再設定しなおせばよい。時間テーブルdは、新しいスタート地点をのぞいて、ふたたび初期化しておく。

• 実装の重さ

全体的なプログラムの分量が大きく、適正時間内にフルスクラッチで組むのはけっこう難しい。迷路問題のいわば"テンプレート"を事前に作っておき、それを適宜拡張修正しながら答案をつくるのが現実的かと思う。

このプログラムは蟻本の迷路bfsを下敷きにしたもので、見通しよく拡張していけて重宝した。

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?