迷路探索のアルゴリズムを考えろという問題。
人生を書き換える者すらいた: 人材獲得作戦・４ 試験問題ほか より。
このアルゴリズムは、やったことはなかったので、やってみました。
で、結果。Lv2 (最短性のチェックはせず、とにかく１本の到達経路を求めることまではできた) までしかできませんでした…orz
とにかく可能な限り G に近づくようにするようにやっていったので、実際には最短ルートがでるはずだとは思いますが、（間違っているかも）どちらにせよ Lv2 ですね…。
次の記事で、筆者曰くこの問題ができたから優秀な人材とは限らないけれど、できない人は”ほぼ確実に”優秀ではない、のではないかと。
このブログの自己紹介欄から「底辺プログラマ。」の一言が消えるのはまだまだ先か…。
以下コード。Java です。無駄に長い。
import java.awt.Point;
//2時間22分
public class MeiroSaitan {
char[][] chars = {
"**************************".toCharArray(),
"*S* * *".toCharArray(),
"* * * * ************* *".toCharArray(),
"* * * ************ *".toCharArray(),
"* * *".toCharArray(),
"************** ***********".toCharArray(),
"* *".toCharArray(),
"** ***********************".toCharArray(),
"* * G *".toCharArray(),
"* * *********** * *".toCharArray(),
"* * ******* * *".toCharArray(),
"* * *".toCharArray(),
"**************************".toCharArray()
};
Character[][] maps = new Character[13][26];
Point current = new Point(0, 0);
Point former = new Point(0, 0);
Point gPlace = new Point(0, 0);
public static void main(String[] args) {
new MeiroSaitan();
}
public MeiroSaitan() {
// S の位置を current に代入
for (int i = 0; i < chars.length; i++) {
for (int j = 0; j < chars[i].length; j++) {
maps[i][j] = new Character(chars[i][j]);
if (maps[i][j].equals('S')) {
current.x = j;
current.y = i;
former.x = j;
former.y = i;
}
if (maps[i][j].equals('G')) {
gPlace.x = j;
gPlace.y = i;
}
}
}
while (!maps[current.y][current.x].equals('G')) { // G に辿り着かない限り
former.x = current.x;
former.y = current.y;
if (whereIsG()[0] == S.RIGHT && whereIsG()[1] == S.DOWN) {
// 下がブロックでなければ
if (canMove(S.DOWN) && !hasGone(S.DOWN))
current.y = current.y + 1;
// 右がブロックでなければ
else if (canMove(S.RIGHT) && !hasGone(S.RIGHT))
current.x = current.x + 1;
// 左がブロックでなければ
else if (canMove(S.LEFT) && !hasGone(S.LEFT))
current.x = current.x - 1;
// 上がブロックでなければ
else if (canMove(S.UP) && !hasGone(S.UP))
current.y = current.y - 1;
//
// 下がブロックでなければ
else if (canMove(S.DOWN) && !isBadRoute(S.DOWN))
current.y = current.y + 1;
// 右がブロックでなければ
else if (canMove(S.RIGHT) && !isBadRoute(S.RIGHT))
current.x = current.x + 1;
// 左がブロックでなければ
else if (canMove(S.LEFT) && !isBadRoute(S.LEFT))
current.x = current.x - 1;
// 上がブロックでなければ
else if (canMove(S.UP) && !isBadRoute(S.UP))
current.y = current.y - 1;
//
else
System.out.println("I can't move!");
} else if (whereIsG()[0] == S.RIGHT && whereIsG()[1] == S.UP) {
// 上がブロックでなければ
if (canMove(S.UP) && !hasGone(S.UP))
current.y = current.y - 1;
// 右がブロックでなければ
else if (canMove(S.RIGHT) && !hasGone(S.RIGHT))
current.x = current.x + 1;
// 左がブロックでなければ
else if (canMove(S.LEFT) && !hasGone(S.LEFT))
current.x = current.x - 1;
// 下がブロックでなければ
else if (canMove(S.DOWN) && !hasGone(S.DOWN))
current.y = current.y + 1;
//
// 上がブロックでなければ
else if (canMove(S.UP) && !isBadRoute(S.UP))
current.y = current.y - 1;
// 右がブロックでなければ
else if (canMove(S.RIGHT) && !isBadRoute(S.RIGHT))
current.x = current.x + 1;
// 左がブロックでなければ
else if (canMove(S.LEFT) && !isBadRoute(S.LEFT))
current.x = current.x - 1;
// 下がブロックでなければ
else if (canMove(S.DOWN) && !isBadRoute(S.DOWN))
current.y = current.y + 1;
//
else
System.out.println("I can't move!");
} else if (whereIsG()[0] == S.LEFT && whereIsG()[1] == S.UP) {
// 左がブロックでなければ
if (canMove(S.LEFT) && !hasGone(S.LEFT))
current.x = current.x - 1;
// 上がブロックでなければ
else if (canMove(S.UP) && !hasGone(S.UP))
current.y = current.y - 1;
// 下がブロックでなければ
else if (canMove(S.DOWN) && !hasGone(S.DOWN))
current.y = current.y + 1;
// 右がブロックでなければ
else if (canMove(S.RIGHT) && !hasGone(S.RIGHT))
current.x = current.x + 1;
//
// 左がブロックでなければ
else if (canMove(S.LEFT) && !isBadRoute(S.LEFT))
current.x = current.x - 1;
// 上がブロックでなければ
else if (canMove(S.UP) && !isBadRoute(S.UP))
current.y = current.y - 1;
// 下がブロックでなければ
else if (canMove(S.DOWN) && !isBadRoute(S.DOWN))
current.y = current.y + 1;
// 右がブロックでなければ
else if (canMove(S.RIGHT) && !isBadRoute(S.RIGHT))
current.x = current.x + 1;
//
else
System.out.println("I can't move!");
} else if (whereIsG()[0] == S.LEFT && whereIsG()[1] == S.DOWN) {
// 左がブロックでなければ
if (canMove(S.LEFT) && !hasGone(S.LEFT))
current.x = current.x - 1;
// 下がブロックでなければ
else if (canMove(S.DOWN) && !hasGone(S.DOWN))
current.y = current.y + 1;
// 右がブロックでなければ
else if (canMove(S.RIGHT) && !hasGone(S.RIGHT))
current.x = current.x + 1;
// 上がブロックでなければ
else if (canMove(S.UP) && !hasGone(S.UP))
current.y = current.y - 1;
//
// 下がブロックでなければ
else if (canMove(S.DOWN) && !isBadRoute(S.DOWN))
current.y = current.y + 1;
// 右がブロックでなければ
else if (canMove(S.RIGHT) && !isBadRoute(S.RIGHT))
current.x = current.x + 1;
// 左がブロックでなければ
else if (canMove(S.LEFT) && !isBadRoute(S.LEFT))
current.x = current.x - 1;
// 上がブロックでなければ
else if (canMove(S.UP) && !isBadRoute(S.UP))
current.y = current.y - 1;
//
else
System.out.println("I can't move!");
}
if (hasGone(current.x, current.y) && !maps[current.y][current.x].equals('G')) {
maps[former.y][former.x] = 'x';
} else if (!maps[current.y][current.x].equals('G')){
maps[current.y][current.x] = '$';
}
// showCurrentState();
}
showCurrentState();
}
private boolean canMove(S s) {
switch (s) {
case UP:
if (maps[current.y - 1][current.x].equals('*')) {
return false;
} else {
return true;
}
case DOWN:
if (maps[current.y + 1][current.x].equals('*')) {
return false;
} else {
return true;
}
case RIGHT:
if (maps[current.y][current.x + 1].equals('*')) {
return false;
} else {
return true;
}
case LEFT:
if (maps[current.y][current.x - 1].equals('*')) {
return false;
} else {
return true;
}
}
return false;
}
private boolean hasGone(int x, int y) {
if (maps[y][x].equals('$') || maps[y][x].equals('x')) {
return true;
}
return false;
}
private boolean hasGone(S s) {
switch (s) {
case UP:
if (maps[current.y - 1][current.x].equals('x') || maps[current.y - 1][current.x].equals('$')) {
return true;
} else {
return false;
}
case DOWN:
if (maps[current.y + 1][current.x].equals('x') || maps[current.y + 1][current.x].equals('$')) {
return true;
} else {
return false;
}
case RIGHT:
if (maps[current.y][current.x + 1].equals('x') || maps[current.y][current.x + 1].equals('$')) {
return true;
} else {
return false;
}
case LEFT:
if (maps[current.y][current.x - 1].equals('x') || maps[current.y][current.x - 1].equals('$')) {
return true;
} else {
return false;
}
}
return false;
}
private boolean isBadRoute(S s) {
switch (s) {
case UP:
if (maps[current.y - 1][current.x].equals('x')) {
return true;
} else {
return false;
}
case DOWN:
if (maps[current.y + 1][current.x].equals('x')) {
return true;
} else {
return false;
}
case RIGHT:
if (maps[current.y][current.x + 1].equals('x')) {
return true;
} else {
return false;
}
case LEFT:
if (maps[current.y][current.x - 1].equals('x')) {
return true;
} else {
return false;
}
}
return false;
}
private void showCurrentState() {
System.out.println(former.x + ", " + former.y + " -> " + current.x + ", " + current.y);
for (int i = 0; i
< maps.length; i++) {
for (int j = 0; j
< maps[i].length; j++) {
System.out.print(maps[i][j]);
}
System.out.println();
}
System.out.println("----------");
}
private S[] whereIsG() {
S[] where = new S[2];
if (current.x < gPlace.x) {
where[0] = S.RIGHT;
} else {
where[0] = S.LEFT;
}
if (current.y < gPlace.y) {
where[1] = S.DOWN;
} else {
where[1] = S.UP;
}
return where;
}
enum S {
RIGHT, LEFT, UP, DOWN;
}
}
