SuperCon2006予選課題 part4

Program 備忘録

Powered by dKingyo ポケットリファレンス | TurboGears | ゲームプログラミング | C言語 | Python


http://d.hatena.ne.jp/studiokingyo/20070415
からの続き


その手の関連資料を探しているうちにおもしろい資料を見つけた。
http://www.misojiro.t.u-tokyo.ac.jp/~tomomi/POWER-POINT/tamura/koukai98/index.htm

さて、
http://www.gsic.titech.ac.jp/supercon/supercon2006/yosen.html
の課題の例の最短経路って以下のような感じではないか？

.  .  .  .  *  .  .  .　　　　　.  .  .  .--*  .  .  .

                        　　　　         |  |           

.  .  *  .  .  .  .  .　　　　　.  .--*--.  .  .  .  .

                        　　　　   |        |           

.  *  .  .  .  .  .  .　　　　　.  *  .  .  .  .  .  .

                        　　　　   |        |           

.  *  .  .  *  .  *  .　　　　　.  *  .  .  *--.--*  .

                        　　　　   |              |     

.  .  .  *  *  .  *  .　　　　　.  .  .  *--*  .  *  .

                        　　　　   |     |  |     |     

.  .  *  *  *  .  *  .　　　　　.  .  *--*  *--.--*  .

                        　　　　   |  |                 

.  *  .  .  .  .  .  .　　　　　.  *--.  .  .  .  .  .

                        

.  .  .  .  .  .  .  .　　　　　.  .  .  .  .  .  .  .
私が手動で求めたものだけど･･･


多分、この思考過程をプログラム化すればよいのだと思うが･･･その思考過程･･･面倒すぎる･･･。
アルゴリズムの過程の一部抜粋としては

  • 「頂点は外側の頂点を優先しつつもその頂点に行く途中に通った方が距離が節約できる頂点があればそれを通る」
  • 一番外側の４つの頂点に注目するそれを元に検索の仕方を変更する。

といった形。
本当に高校生がC言語でこんなに組めるか！？素晴らしい･･･。
私はRubyでもないと作業が効率的ではなくてさじを投げてしまう。おｒｚ。