PHPとJavaScriptで『人材獲得作戦・４ 試験問題』を解いてみた（つづく。）
今さらですが、試験問題はここにあります。
http://okajima.air-nifty.com/b/2010/01/post-abc6.html
幅優先検索ロジックでPHPで解いてみまして、そして、同じロジックでJavaScriptで探索経過を再現してみましたが。
まだ、解けていない部分があります。
それは、最短経路ではない。orz
まあ、自分なりの不完全な答えを恥ずかしながらお見せします。ｗ
後日に、最短経路込みの回答を追記します。
- ここに実際の画面を見れます。
http://benny.sakura.ne.jp/tmp/run.php
ソース
<?php
class map {
public $map;
public $sx;
public $sy;
public $queue = array();
public $history_map;
function __construct(){
$map = file("./map.txt");
foreach($map as $row => $line) {
$line =str_split($line);
foreach($line as $col => $word) {
$this->map[$row][$col] = $word;
//Sの原点を設定
if($word == "S") {
#キューを初期化
$this->queue[] = array($row,$col);
}
}
}
}
function run()
{
while ($this->_getNext()){}
}
#次へ行けるポイントを見つける
private function _getNext()
{
#キューが空になったら探索を終了させる
if(!$this->queue) return false;
#キューの先頭から今回の探索起点ポイントをゲット
list($sx,$sy) = array_shift($this->queue);
if(!$this->history_map) {
$this->history_map[$sx][$sy] = $this->map;
}
#方向を見る,順番は↓ → ← ↑
$nextPoint['down'] = array($sx, $sy + 1);
$nextPoint['right'] = array($sx + 1, $sy);
$nextPoint['left'] = array($sx - 1, $sy);
$nextPoint['up'] = array($sx, $sy - 1);
#四つの方向から次へ行けるポイントをすべて探し出す
foreach ($nextPoint as $v)
{
list($x, $y) = $v;
switch($this->map[$x][$y])
{
#「*」だったら、殺す
case "*":
continue;
break;
#「G」だったら、描画して終了！
case "G":
$this->_print_map($this->history_map[$sx][$sy]);
return false;
break;
#空白だったら且つ未探索ポイントだったら、キューに入れる
default:
if(!$this->history_map[$x][$y]){
array_unshift($this->queue, $v);
$this->history_map[$x][$y] = $this->history_map[$sx][$sy];
$this->history_map[$x][$y][$x][$y] = "#";
}
continue;
break;
}
}
return true;
}
#経路を描画する
private function _print_map($map)
{
echo "<pre>";
foreach ($map as $row => $line) {
foreach ($line as $word) {
echo $word;
}
}
echo "</pre><br />";
}
}
$map = new map();
$map->run();
?>
<script type="text/javascript" src="jquery.js"></script>
<script>
$(document).ready(function(){
//マップ制御実行
$("#map").map_run();
});
(function($){
$.fn['map_run'] = function(){
var map = new Array();
var history_map = new Array();
var map_dom = $(this);
var sx;
var sy;
var queue = new Array();
var n = 0;
var timerID;
var _fn =
{
init : function (){
var rows = map_dom.text().split('\n');
for (var x = 0; x < rows.length; x++){
var line = rows[x].split('');
map[x] = [];
for (var y = 0; y < line.length; y++){
map[x][y] = line[y];
if(line[y] == "S"){
queue[0] = [x,y];
history_map[x+"_"+y] = this.get_new_map_str(map_dom.text());
}
}
}
},
run : function (){
timerID = window.setInterval(function (){
_fn.get_next();
}, 100);
},
get_next : function (){
//キューが空になったら探索を終了させる
if(queue.length == 0) return false;
//キューの先頭から今回の探索起点ポイントをゲット
var sxy = queue.shift();
sx = sxy[0];
sy = sxy[1];
this.print_map(history_map[sx+"_"+sy]);
//方向を見る
var nextPoint = [];
nextPoint['down'] = [sx, sy + 1];
nextPoint['right'] = [sx + 1, sy];
nextPoint['left'] = [sx - 1, sy];
nextPoint['up'] = [sx, sy - 1];
//四つの方向から次へ行けるポイントをすべて探し出す
for (next in nextPoint) {
var x = nextPoint[next][0];
var y = nextPoint[next][1];
switch (map[x][y]) {
//「*」だったら、殺す
case '*':
continue;
break;
//「G」だったら、描画して終了！
case 'G':
this.print_map(history_map[sx+"_"+sy]);
clearInterval(timerID);
return false;
break;
default:
if(!history_map[x+"_"+y]){
queue.unshift([x,y]);
history_map[x+"_"+y] = this.get_new_map_str(history_map[sx+"_"+sy], x, y);
}
continue;
break;
}
}
return true;
},
print_map : function (map){
map_dom.text(map);
},
get_new_map_str : function (map_str, step_x, step_y) {
var rows = map_str.split('\n');
var map_array = [];
for (var x = 0; x < rows.length; x++){
var line = rows[x].split('');
map_array[x] = [];
for (var y = 0; y < line.length; y++){
map_array[x][y] = line[y];
}
}
if(step_x && step_y){
map_array[step_x][step_y] = "#";
}
for (var x = 0; x < map_array.length; x++) {
line[x] = map_array[x].join("");
}
return line.join("\n");
}
}
_fn.init();
_fn.run();
};
})(jQuery);
</script>
<pre id ="map" >
**************************
*S* * *
* * * * ************* *
* * * ************ *
* * *
************** ***********
* *
** ***********************
* * G *
* * *********** * *
* * ******* * *
* * *
**************************
</pre>
