読者です 読者をやめる 読者になる 読者になる

samayotta.show()

好きな映画は『たまこラブストーリー』です。

AOJ0588,Cheese

二つ目はBFS。

チーズ | Aizu Online Judge

 

AOJ0588,Cheese

 

解説

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

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

  • 経過時間の繰り越し

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

  • 実装の重さ

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

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

 

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

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