コグノスケ


link 未来から過去へ表示(*)  link 過去から未来へ表示

link もっと前
2010年1月16日 >>> 2010年1月7日
link もっと後

2010年1月12日

タイムトライアルは苦手です

研究室のWikiでIKeJIから教えてもらったこの問題(参照: 人生を書き換える者すらいた。: 人材獲得作戦4試験問題ほか)にトライしてみました。

手元にあった環境とC言語でトライしたところ、19:38開始、21:18終了、所要時間1時間40分でした。回答はこんな感じです。

私の回答の出力結果
$ ./a.out < meiro.dat
found the goal depth=60
**************************
*S* * $$$                *
*$* *$$*$ *************  *
*$* $$* $  ************  *
*$$$$*  $$$$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$  * $$$$$$$$$$$$$G  *
*  *$$$$$$*********** *  *
*    *        ******* *  *
*       *                *
**************************

出力結果は上記サイトの基準でいうLv4達成(※)です。

苦戦したところはダイクストラ法の実装です。ダイクストラ法なんかは基本中の基本のアルゴリズムですが、結構忘れていて手間取りました。

一応link ソースコードも載せておきます。頭に修正BSDライセンスの条文を追加した以外、全てそのままです。

リファクタリングも何もしていませんので、変なコメント、グローバル変数乱発、意味不明な変数名、デバッグ用コード、ゴールできないときハングするバグ(※2)も恥ずかしながらそのままです。

迷路一歩進む度に、迷路の全域をチェックするなどモサい実装ですが、これが現状発揮できる自身の実力の一つであることには違いないです。よって今後も精進あるのみです。

(※)ダイクストラ法は常に最適解、この問題の場合でいえばゴールまでの最短距離を得られるためです。証明は習った気がしますが忘れました…。

(※2)ゴールへの経路がない場合「not found the goal」と出力しますが、returnし忘れているため、その後のパスのバックトレース部分に突入してしまい、無限ループに陥ってハングします。
日記を書いているときに気がつきました。ひどすぎですね、これ。

編集者:すずき(2010/01/12 22:43)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



link もっと前
2010年1月16日 >>> 2010年1月7日
link もっと後

管理用メニュー

link 記事を新規作成

<2010>
<<<01>>>
-----12
3456789
10111213141516
17181920212223
24252627282930
31------

最近のコメント5件

  • link 21年3月13日
    すずきさん (03/05 15:13)
    「あー、このプログラムがまずいんですね。ご...」
  • link 21年3月13日
    emkさん (03/05 12:44)
    「キャストでvolatileを外してアクセ...」
  • link 24年1月24日
    すずきさん (02/19 18:37)
    「簡単にできる方法はPowerShellの...」
  • link 24年1月24日
    KKKさん (02/19 02:30)
    「追伸です。\nネットで調べたらマイクロソ...」
  • link 24年1月24日
    KKKさん (02/19 02:25)
    「私もエラーで困ってます\n手動での回復パ...」

最近の記事3件

  • link 24年3月25日
    すずき (03/26 03:20)
    「[Might and Magic Book One TASのその後] 目次: Might and Magicファミコン版以前(...」
  • link 21年10月4日
    すずき (03/26 03:14)
    「[Might and Magicファミコン版 - まとめリンク] 目次: Might and Magicファミコン版TASに挑...」
  • link 24年3月19日
    すずき (03/20 02:52)
    「[モジュラージャックの規格] 古くは電話線で、今だとEthernetで良く見かけるモジュラージャックというコネクタとレセプタク...」
link もっとみる

こんてんつ

open/close wiki
open/close Linux JM
open/close Java API

過去の日記

open/close 2002年
open/close 2003年
open/close 2004年
open/close 2005年
open/close 2006年
open/close 2007年
open/close 2008年
open/close 2009年
open/close 2010年
open/close 2011年
open/close 2012年
open/close 2013年
open/close 2014年
open/close 2015年
open/close 2016年
open/close 2017年
open/close 2018年
open/close 2019年
open/close 2020年
open/close 2021年
open/close 2022年
open/close 2023年
open/close 2024年
open/close 過去日記について

その他の情報

open/close アクセス統計
open/close サーバ一覧
open/close サイトの情報

合計:  counter total
本日:  counter today

link About www.katsuster.net
RDFファイル RSS 1.0

最終更新: 03/26 03:20