人生を書き換える者すらいた。: 人材獲得作戦・４ 試験問題ほか
http://okajima.air-nifty.com/b/2010/01/post-abc6.html
先週あたり、はてブ界隈でもちょっとにぎわっていたようで、今さらながら答えてみました。詳細は上記元記事参照。
結局、制限時間の3時間はちょっと越えたかな…。途中に別件が挟まったから正確な時間はわからないけど。経路探索はダイクストラ法を卒研で使ったので、今回の問題の解法もまあまあイメージできたんだけど、さすがにこれは遅いよなぁ。
最初Cで書き始めて、ほぼ書きあがったところでPCに実行環境が整ってないことに気づいてWSH(JScript)に書き換えたりした。最初からこっちで書いてたら2時間ちょいくらいで書けてたかもね。それでも遅いことに変わりはないけど。
せっかくだからソース晒すぜ。もともとCで書いてたことと、WSH+JScriptの書き方よく知らないってのもあってかなりグダグダ。
<?xml version="1.0" encoding="Shift_JIS" standalone="yes" ?>
<package>
<job id="ShortestPath">
<?job error="True" debug="True" ?>
<object id="objFs" progid="Scripting.FileSystemObject" />
<script language="JavaScript">
<![CDATA[
// Map Size
var MAP_SIZE_X = 32; // Map Size(横)
var MAP_SIZE_Y = 16; // Map Size(縦)
// Map Status
var MAPST_START = 0x80; // "S": Start
var MAPST_GOAL = 0x40; // "G": Goal
var MAPST_WALL = 0x20; // "*": Wall
var MAPST_FOOTPRINT = 0x10; // "$": FootPrint
var DIST_MAX = 0xFFFF; // Startからの距離、初期値
var buf = new Array(MAP_SIZE_X);
var Map = new Array(MAP_SIZE_X); // Map Data
var DistFromStart = new Array(MAP_SIZE_X); // Startからの距離
var myx, myy, goal, goalx, goaly;
// 2次元配列作成
for(i=0; i<MAP_SIZE_X; ++i) {
Map[i] = new Array(MAP_SIZE_Y);
DistFromStart[i] = new Array(MAP_SIZE_Y);
}
// FileからMap Dataの読み込み
var objTs = objFs.OpenTextFile("map.txt", 1, false);
myy = 0;
do {
buf=objTs.ReadLine();
WScript.Echo(buf); // Map Data表示
for(myx=0; myx<buf.length; ++myx) {
if(buf.charAt(myx) == "S") {
Map[myx][myy] = MAPST_START;
} else if(buf.charAt(myx) == "G") {
Map[myx][myy] = MAPST_GOAL;
} else if(buf.charAt(myx) == " ") {
Map[myx][myy] = 0x00;
// } else if(buf.charAt(myx) == "*") {
} else {
Map[myx][myy] = MAPST_WALL;
}
}
if(myy+1 > MAP_SIZE_Y) break;
++myy;
}while(!objTs.AtEndOfStream);
objTs.Close();
// Startからの距離配列を初期化
for(myx=0; myx<MAP_SIZE_X; ++myx) {
for(myy=0; myy<MAP_SIZE_Y; ++myy) {
if(Map[myx][myy] == MAPST_START) {
DistFromStart[myx][myy] = 0; // Start位置
} else {
DistFromStart[myx][myy] = DIST_MAX; // Start以外は未知、無限遠と仮定
}
}
}
while(1) {
for(myx=0; myx<MAP_SIZE_X; ++myx) {
for(myy=0; myy<MAP_SIZE_Y; ++myy) {
if(DistFromStart[myx][myy] != DIST_MAX) {
// 到達可能であれば足を伸ばす
// 上
if(myy > 0) {
if((Map[myx][myy-1] & MAPST_GOAL)) {
// Goalにぶつかった時点で最短のはず
DistFromStart[myx][myy-1] = DistFromStart[myx][myy] + 1;
goalx = myx;
goaly = myy-1;
goal = 1;
} else if((Map[myx][myy-1] & (MAPST_START | MAPST_WALL)) == 0x00) {
if(DistFromStart[myx][myy-1] > (DistFromStart[myx][myy] + 1)) {
// 最短距離を更新する
DistFromStart[myx][myy-1] = DistFromStart[myx][myy] + 1;
}
}
}
// 右
if(myx < MAP_SIZE_X) {
if(Map[myx+1][myy] & MAPST_GOAL) {
// Goalにぶつかった時点で最短のはず
DistFromStart[myx+1][myy] = DistFromStart[myx][myy] + 1;
goalx = myx+1;
goaly = myy;
goal = 1;
} else if((Map[myx+1][myy] & (MAPST_START | MAPST_WALL)) == 0x00) {
if(DistFromStart[myx+1][myy] > (DistFromStart[myx][myy] + 1)) {
// 最短距離を更新する
DistFromStart[myx+1][myy] = DistFromStart[myx][myy] + 1;
}
}
}
// 下
if(myy < MAP_SIZE_Y) {
if(Map[myx][myy+1] & MAPST_GOAL) {
// Goalにぶつかった時点で最短のはず
DistFromStart[myx][myy+1] = DistFromStart[myx][myy] + 1;
goalx = myx;
goaly = myy+1;
goal = 1;
} else if((Map[myx][myy+1] & (MAPST_START | MAPST_WALL)) == 0x00) {
if(DistFromStart[myx][myy+1] > (DistFromStart[myx][myy] + 1)) {
// 最短距離を更新する
DistFromStart[myx][myy+1] = DistFromStart[myx][myy] + 1;
}
}
}
// 左
if(myx > 0) {
if(Map[myx-1][myy] & MAPST_GOAL) {
// Goalにぶつかった時点で最短のはず
DistFromStart[myx-1][myy] = DistFromStart[myx][myy] + 1;
goalx = myx-1;
goaly = myy;
goal = 1;
} else if((Map[myx-1][myy] & (MAPST_START | MAPST_WALL)) == 0x00) {
if(DistFromStart[myx-1][myy] > (DistFromStart[myx][myy] + 1)) {
// 最短距離を更新する
DistFromStart[myx-1][myy] = DistFromStart[myx][myy] + 1;
}
}
}
}
if(goal == 1) break;
}
if(goal == 1) break;
}
if(goal == 1) break;
}
// Goalから足跡を逆にたどっていく
myx = goalx;
myy = goaly;
while(1) {
// 上
if(myy > 1) {
if(Map[myx][myy-1] == MAPST_START) break; // 逆探索終了
if(DistFromStart[myx][myy-1] == (DistFromStart[myx][myy] - 1)) {
Map[myx][myy-1] = MAPST_FOOTPRINT;
myy = myy-1;
continue;
}
}
// 右
if(myx < MAP_SIZE_X) {
if(Map[myx+1][myy] == MAPST_START) break; // 逆探索終了
if(DistFromStart[myx+1][myy] == (DistFromStart[myx][myy] - 1)) {
Map[myx+1][myy] = MAPST_FOOTPRINT;
myx = myx+1;
continue;
}
}
// 下
if(myy < MAP_SIZE_Y) {
if(Map[myx][myy+1] == MAPST_START) break; // 逆探索終了
if(DistFromStart[myx][myy+1] == (DistFromStart[myx][myy] - 1)) {
Map[myx][myy+1] = MAPST_FOOTPRINT;
myy = myy+1;
continue;
}
}
// 左
if(myx > 1) {
if(Map[myx-1][myy] == MAPST_START) break; // 逆探索終了
if(DistFromStart[myx-1][myy] == (DistFromStart[myx][myy] - 1)) {
Map[myx-1][myy] = MAPST_FOOTPRINT;
myx = myx-1;
continue;
}
}
break; // ここに来るのはおかしい
}
// 最短ルートを載せて結果表示
for(myy=0; myy<MAP_SIZE_Y; ++myy) {
buf = "";
for(myx=0; myx<MAP_SIZE_X; ++myx) {
if(Map[myx][myy] == MAPST_START) {
buf += "S";
} else if(Map[myx][myy] == MAPST_GOAL) {
buf += "G";
} else if(Map[myx][myy] == MAPST_WALL) {
buf += "*";
} else if(Map[myx][myy] == MAPST_FOOTPRINT) {
buf += "$";
} else {
buf += " ";
}
}
WScript.Echo(buf);
}
]]>
</script>
</job>
</package>
JScriptソースを適当な名前("ShortestPath.wsf"とか)で保存、入力マップファイル"map.txt"も同じフォルダに入れておく。そしておもむろにコマンドプロンプトから"cscript ShortestPath.wsf"。
入力ファイル"map.txt"はこんな感じ。
**************************
*S* * *
* * * * ************* *
* * * ************ *
* * *
************** ***********
* *
** ***********************
* * G *
* * *********** * *
* * ******* * *
* * *
**************************
すると、出力される結果はこう。
**************************
*S* * $$$ *
*$* *$$*$ ************* *
*$* $$* $$$************ *
*$$$$* $$$$$ *
**************$***********
* $$$$$$$$$$$$$ *
**$***********************
* $$$$$*$$$$$$$$$$$$$$G *
* * $$$ *********** * *
* * ******* * *
* * *
**************************
この試験問題に取り組んでわかったことは、「もっとコード書こうぜ、俺」ってことかなー。この程度のボリュームのソースでも、胡散臭さがぷんぷんするもんな。もう長いこと、組み込み(言語はC)でメンテナンス程度しかコードいじってない。
ま、ちょっとこれきっかけでプログラミング熱が高まってきたので、よしとしよう。よしでお願いします。
