試験問題を解いてみました

人生を書き換える者すらいた。: 人材獲得作戦・４　試験問題ほか
http://okajima.air-nifty.com/b/2010/01/post-abc6.html

こういう問題を解くの楽しいですね。仕事では滅多に使いませんが。

回答

動作ページ
http://hagino3k.appspot.com/sample/keiro.html

Cで解こうとした人が多かったみたいですけど、Cなんて8年以上触ってないのでJavaScriptでやってます。スタート地点からどれだけの距離か塗りつぶしていって、ゴールから距離が減る方向に移動していく方式で。余裕で1時間以上かかっているのと、問題のページへトラバ飛ばしてる他の人の回答より行数が圧倒的に多いです。

コード

繰り返し呼ばれる箇所で関数生成しまくってるので動作は遅いのですが、書きやすさ優先でこうなってます。業務エンジニアっぽいというか、とりあえずクラスを作らないと気が済まないという自分の悪い癖が出てるコードですね。

function start() {
  clear();
  createMaze();
  setDistance();
  findRoute();
  output();
}

/**
 * 迷路情報
 */
var maze = {
  width : 0,
  height : 0,
  data : null,
  start : null,
  end : null,
  get : function(x, y) {
    return this.data[x][y];
  },
  init : function() {
    this.data = [];
    for (var i=0; i<this.width; i++) {
      this.data.push(new Array(this.height));
    }
  }
};

/**
 * 各タイルを表現するクラス
 */
var Tile = function(x, y, c) {
  Tile.prototype.init.apply(this, arguments);
}
Tile.prototype = {
  /**
   * コンストラクタ
   * @param {Number} x X座標
   * @param {Number} y Y座標
   * @param {String} c 文字("S" or " " or "*" or "G")
   */
  init : function(x, y, c) {
    this.code = c;
    this.x = x;
    this.y = y;
    this.visited = false;
    this.distance = Infinity;
    this.enable = c === " " || c === "G";
    this.isGoal = c === "G";
    this.kakutei = false;
  },

  /**
   * 隣接するタイルの取得
   */
  getNext : function(visited) {
    var ret=[], x=this.x, y=this.y;
    var points=[{x:x+1,y:y},{x:x,y:y+1},{x:x-1,y:y},{x:x,y:y-1}];

    points.forEach(function(p) {
      var d = maze.get(p.x, p.y);
      if (d && d.enable && (visited && d.visited || !visited && !d.visited)) {
        ret.push(d);
        d.visited = true;
      }
    });
    return ret;
  },

  getPrev : function() {
    var tiles = this.getNext(true);
    var ret = tiles.filter(function(t) {
      return t.distance < this.distance;
    }, this);
    return ret && ret[0];
  },

  setDistance : function(dist) {
    this.distance = dist;
  },

  toChar : function() {
    return this.kakutei ? "$" : this.code;
  }
}

/**
 * 入力の読み込み
 */
function createMaze() {
  var inputText = document.getElementById('inputarea').value;

  // 最後の*以降の改行やスペースを除去
  inputText = (function(str){
    if (str.lastIndexOf("*") === str.length-1) {
      return str;
    } else {
      return str.substring(0, str.lastIndexOf("*")+1);
    }
  })(inputText);

  maze.width  = inputText.indexOf(String.fromCharCode(10));
  maze.height = (inputText.length + 1)/(maze.width + 1);

  if ((inputText.length + 1)%(maze.width + 1) !== 0) {
    document.getElementById('outputarea').value =  "invalid maze";
    throw "invalid maze"
  }
  maze.init();

  var x=0, y=0;
  for(var i=0; i<inputText.length; i++) {
    var c = inputText.charAt(i);
    if (c == String.fromCharCode(10)) {
      y++;
      x=0;
      continue;
    }
    var d = new Tile(x, y, c);
    maze.data[x][y] = d; 
    if (c === 'S') {
      maze.start = d;
    }else
    if (c === 'G') {
      maze.goal = d;
    }
    x++;
  }
};

/**
 * 各タイルにスタート地点からの距離を設定する
 */
function setDistance() {
  var reachGoal;
  (function(tiles, distance) {
    var nextTiles = [];
    tiles.forEach(function(t) {
      t.setDistance(distance);
      if (t.isGoal) {
        reachGoal = true;
      } else {
        Array.prototype.push.apply(nextTiles, t.getNext());
      }
    });
    if (!reachGoal) {
      arguments.callee(nextTiles, ++distance);
    }
  })([maze.start], 0);
};

/**
 * 最短ルート上のタイルにマークを付ける
 */
function findRoute() {
  (function(tile) {
    var t = tile.getPrev();
    if (t) {
      t.kakutei = true;
      arguments.callee(t);
    }
  })(maze.goal);
};

/**
 * 画面出力
 */
function output() {
  var result = "";
  for(var y=0; y<maze.height; y++){
    for(var x=0; x<maze.width; x++){
      result+=maze.get(x, y).toChar();
    }
    result+=String.fromCharCode(10);
  }
  document.getElementById('outputarea').value = result;
};

/**
 * テキストエリアのクリア
 */
function clear() {
  document.getElementById('outputarea').value = "";
}