遅ればせながら、
人材獲得作戦・４ 試験問題
を解いてみました。A*（えーあすた）というアルゴリズムは知らなかったので
「反復深化深さ優先探索」で解いてみました。意外とスッキリ書けたかなぁ。
かかった時間は大体１時間くらいでした。
ちなみに、空白の多い迷路だと、探索に時間がかかりすぎるので Lv3判定ですねｗ
人材獲得作戦・４ 試験問題
を解いてみました。A*（えーあすた）というアルゴリズムは知らなかったので
「反復深化深さ優先探索」で解いてみました。意外とスッキリ書けたかなぁ。
かかった時間は大体１時間くらいでした。
ちなみに、空白の多い迷路だと、探索に時間がかかりすぎるので Lv3判定ですねｗ
public class Maze { char route[][]; int depth; String maze[] = { "**************************", "*S* * *", "* * * * ************* *", "* * * ************ *", "* * *", "************** ***********", "* *", "** ***********************", "* * G *", "* * *********** * *", "* * ******* * *", "* * *", "**************************", }; public static void main(String[] args) { new Maze().start(); } void start() { int sy = 0; int sx = 0; for (String s : maze) { sx = s.indexOf('S'); if (sx > -1) { break; } sy++; } for (;;) { route = new char[maze.length][maze[0].length()]; if (find(sx, sy , 0)) { answer(); break; } depth++; } } boolean find(int x, int y,int count) { if (count == depth) { if (screen(x, y) == 'G') { return true; } return false; } if (route[y][x] != '\0') { return false; } if (screen(x, y) == '*') { return false; } route[y][x] = '$'; if (find(x + 1, y , count + 1) || find(x - 1, y, count + 1) || find(x, y + 1, count + 1) || find(x, y - 1, count + 1)) { return true; } route[y][x] = '\0'; return false; } void answer() { for (int y = 0; y < maze.length; y++) { for (int x = 0; x < maze[0].length(); x++) { if (route[y][x] != '\0' && screen(x,y) != 'S') { System.out.print(route[y][x]); } else { System.out.print(screen(x, y)); } } System.out.println(); } System.out.println(); } char screen(int x, int y) { return maze[y].charAt(x); } }
実行結果************************** *S* * $$$$ * *$* *$$* $************* * *$* $$* $$************ * *$$$$* $$$$$ * **************$*********** * $$$$$$$$$$$$$ * **$*********************** * $$$$$* $$$$$$$$$$$$$G * * * $$$$*********** * * * * ******* * * * * * **************************
