2010-01-13

http://okajima.air-nifty.com/b/2010/01/post-abc6.html

少し遅れた感があるけど、解いてみた。

出力がテキストでないけど・・・。

仕事の合間を使ってやったものの、昼前に始めたのが5時頃にようやくできる程度。

これを25分とは尋常じゃないな、大口叩くだけあってよっぽど優秀なんだろう。

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"&gt;

<html&gt;

<head&gt;
<meta http-equiv="Content-Type" content="text/html; charset=shift_jis"&gt;
<meta http-equiv="Content-Language" content="ja"&gt;
<meta http-equiv="Content-Script-Type" content="text/javascript"&gt;
<meta http-equiv="Content-Style-Type" content="text/css"&gt;
<style type="text/css"&gt;
<!--

pre {
  font-family: monospace;
}

--&gt;
</style&gt;
<script type="text/javascript"&gt;
<!--

window.onload = function() {

  var q = new Map();
  q.load("maptest.txt");
  q.search();

  var answer = document.getElementsByTagName("pre").item(0);
  var answerText = "\r\n";
  for(var ix = 0; ix < q.route.length; ix++) {
    answerText += q.route[ix].join("") + "\r\n";
  }
  answer.firstChild.data = answerText;

  alert("終了しました。");
};

/** マップオブジェクト
 */
function Map() {
  this.ymap = [];
  this.route = [];
}

//マップの読み込み
Map.prototype.load = function(filePath) {
 //ファイルシステム
  var fileSystem = new ActiveXObject("Scripting.FileSystemObject");

 //ファイル読み込み
  var file = fileSystem.OpenTextFile(filePath);
  while(!file.AtEndOfLine) {
    var fileBuffer = file.ReadLine();
    this.ymap.push(fileBuffer.split(""));
  }
  file.Close();

  fileSystem = null;
};

//マップの探索
Map.prototype.search = function() {

  var that = this;

 //マップコピー
  var ymap = this.ymap.concat();
  for(var y = 0; y < ymap.length; y++) {
    ymap[y] = ymap[y].concat();
    for(var x = 0; x < ymap[y].length; x++) {
      if(ymap[y][x] == "S")
        var start = new MapNode(y, x);
      if(ymap[y][x] == "G")
        var goal = new MapNode(y, x);
    }
  }

  var openList = [];
  var closeList = [];

  start.costf = start.distance(goal);
  openList.push(start);

 //経路探索
  while(openList.length &gt; 0) {
    var node = openList.shift();
   //探索終了
    if(goal.equal(node)) {
      createRoute(node);
      break;
    }
    closeList.push(node);

   //隣接ノードの作成
    var tonari = [];
    if( ymap[node.positionY][node.positionX - 1] == " "
     || ymap[node.positionY][node.positionX - 1] == "G" )
      tonari.push(new MapNode(node.positionY, node.positionX - 1, node));
    if( ymap[node.positionY - 1][node.positionX] == " "
     || ymap[node.positionY - 1][node.positionX] == "G" )
      tonari.push(new MapNode(node.positionY - 1, node.positionX, node));
    if( ymap[node.positionY][node.positionX + 1] == " "
     || ymap[node.positionY][node.positionX + 1] == "G" )
      tonari.push(new MapNode(node.positionY, node.positionX + 1, node));
    if( ymap[node.positionY + 1][node.positionX] == " "
     || ymap[node.positionY + 1][node.positionX] == "G" )
      tonari.push(new MapNode(node.positionY + 1, node.positionX, node));

   //隣接ノード検索
    for(var tx = 0; tx < tonari.length; tx++) {
      var openIn = false;
      var closeIn = false;
      tonari[tx].cost = node.cost + 1;
      var costf = tonari[tx].cost + tonari[tx].distance(goal);
      tonari[tx].costf = costf;

     //オープンリストから検索し入れ替える。
      for(var ox = 0; ox < openList.length; ox++) {
        if(tonari[tx].equal(openList[ox])) {
          openIn = true;
          if(costf < openList[ox].costf) {
            openList.splice(ox, 1);
            push(openList, tonari[tx]);
          }
          break;
        }
      }
     //クローズリストから検索し、オープンリストへ移す。
      for(var cx = 0; cx < closeList.length; cx++) {
        if(tonari[tx].equal(closeList[cx])) {
          closeIn = true;
          if(costf < closeList[cx].costf) {
            closeList.splice(cx, 1);
            push(openList, tonari[tx]);
          }
          break;
        }
      }
     //どちらにもない場合、オープンリストへ追加する。
      if(!openIn &amp;amp;&amp;amp; !closeIn)
        push(openList, tonari[tx]);
    }
  }

 //適切な位置に追加する。
  function push(array, item) {
    for(var ix = 0; ix < array.length; ix++) {
      if(item.costf < array[ix].costf) {
        array.splice(ix, 0, item);
        return;
      }
    }
    array.push(item);
  }

 //ルートマップの作成
  function createRoute(lastNode) {
    var node = lastNode.parent;
    while(node.parent) {
      ymap[node.positionY][node.positionX] = "$";
      node = node.parent;
    }
    that.route = ymap;
  }
};

/** マップノード
 */
function MapNode(y, x, parentNode) {
  this.positionY = y;
  this.positionX = x;
  this.parent = parentNode;
  this.cost = 0;
  this.costf = 0;
}

//同一ノードかチェックする。
MapNode.prototype.equal = function(targetNode) {
  if( this.positionY == targetNode.positionY
   &amp;amp;&amp;amp; this.positionX == targetNode.positionX )
    return true;
  return false;
};

//直線距離を求める。
MapNode.prototype.distance = function(targetNode) {
  sabunY = this.positionY - targetNode.positionY;
  sabunX = this.positionX - targetNode.positionX;
  return sabunY ^ 2 + sabunX ^ 2;
};

// --&gt;
</script&gt;
<title&gt;経路探索:A*</title&gt;
</head&gt;
<body&gt;

<pre&gt;&amp;nbsp;</pre&gt;

</body&gt;
</html&gt;
  • そうは言っても、やっぱりあいつは偉そうだけどね。 こんなプログラムできなくても仕事にはなんの問題もないよ。

  • コンピュータサイエンスの教育を受けた人や、ACM/ICPCとかtop coderとかやってる人なら、このての問題はすぐ解けるよ 解けない(問題を知らない、解きかたを知らない)と、はずかしいレ...

    • 増田のelegantな解答を拝見したい

      • 34分 現役のときに比べて腕が鈍ってるなあ ソースは汚いよ 同じところを二回訪れないことに注意して、次の状態をキューに入れていけばいいだけ 隣は距離1なのでただのFIFOでいい 重み...

        • ワープあり迷宮とかだったらもっと楽しかったのにw

          • 単純にグラフ作ってdijkstraで解けるような拡張だとつまらない 入力のサイズが大きすぎて、普通の解法が通用しなくて、計算量を減らす必要があるとかだと楽しい 例えば、このタイプの...

            • こういう話題を見てると、俺ってつくづくプログラミングそのものには興味が無いなーって思う。 色々小細工してリソースを効率的に使うとか全く興味が無い。どうでもいいから適当に...

              • リソース減らすってのは、技術というより、現実優先なんだよね。 プロダクトを実際に作ると、どうしても、複数のプログラムが一緒に動いていたり、 メモリ減らすとチップを1つ下の...

                • そういえば、昔、巨大なデーターを扱うプログラムで 遅いというクレームがついて みんなで、早くしましょう。 増田さんの担当分は3時間未満になるようにしてください。って言われ...

                  • その時点ですでに俺のパートは1時間前後だったわけだが。 なら、納期ギリギリまでボケッと遊ぶなり別の勉強するなりして自分の担当分には手を加えず、提出する時に「なんとかが...

            • まずは、巨大な迷路を書くプログラムからだな。 学生時代だったらアルゴリズムを覚えていたので数十分だが いまだと数時間はかかりそう。 とりあえず、巨大な迷路データーが無いこ...

  • これで40分。 タイムアタックってことでアルゴリズムは全幅探索で書き上げました。 エラーチェック皆無。 A*ならもう5分ほど延びるかな? using System;using System.Collections.Generic;using System.L...

    • [増田@hatelabo.jp]gmcs test.cs -r:System.Xml.Linq -out:test.exe test.cs(108,12): warning CS0660: `Maze.Position' defines operator == or operator != but does not override Object.Equals(object o) test.cs(108,12): warning CS0661: `Maze.Position' define...

    • なんか、経路問題だけあって、できてる人のほうが多い印象だよね。 所詮プログラムなんだから、普通にだれでもできるよねぇ。 所詮やっぱり、プログラマはブルーワーカーか アルゴ...

記事への反応(ブックマークコメント)

ログイン ユーザー登録
ようこそ ゲスト さん