「人材獲得作戦・４ 試験問題ほか」という記事で取り上げられている迷路の最短経路を求める問題をJavaで解いてみました。
ファイル入出力以外は、ほとんどCで書いても変わらないようなコードです。
一応、検索しないで1時間くらいでした。
ファイル入出力以外は、ほとんどCで書いても変わらないようなコードです。
一応、検索しないで1時間くらいでした。
import java.io.File;
import java.util.Scanner;
public class Maze {
public static void main(String[] args) throws Exception {
new Maze().run();
}
final int MAXSIZE = 128 * 128;
final int START = 0;
final int WALL = -1;
final int BLANK = -2;
final int GOAL = -3;
final int ROUTE = -4;
final boolean AnswerType = true; // falseで全解出力
int[] ban = new int[MAXSIZE];
int[] answer = new int[MAXSIZE];
int xsize;
int ysize;
int bansize;
int startpos;
int goalpos;
void run() throws Exception{
read("maze.txt");
solve();
}
void read(String filename) throws Exception {
Scanner scan = new Scanner(new File(filename));
String s;
int i, p;
// 配列オーバーフローとかはチェックしない
p = 0;
for(ysize = 0; scan.hasNext(); ysize++){
s = scan.nextLine();
for(i = 0; i < s.length(); i++){
switch(s.charAt(i)){
case '*' : ban[p] = WALL; break;
case ' ' : ban[p] = BLANK; break;
case 'S' : ban[p] = START; startpos = p; break;
case 'G' : ban[p] = GOAL; goalpos = p; break;
}
p++;
}
xsize = i;
}
bansize = xsize * ysize;
}
void solve(){
for(int i = 0; i < bansize; i++) answer[i] = ban[i];
// mark
int level = mark();
// 戻り道を探す
search(goalpos, level);
}
int mark(){
int p;
int level;
for(level = 0; ; level++){
for(p = 0; p < bansize; p++){
if(ban[p] == level){
// 枠のチェックなし、というかここはキューに積む方がいい。
if(ban[p - 1] == BLANK) ban[p - 1] = level + 1;
if(ban[p + 1] == BLANK) ban[p + 1] = level + 1;
if(ban[p - xsize] == BLANK) ban[p - xsize] = level + 1;
if(ban[p + xsize] == BLANK) ban[p + xsize] = level + 1;
if(ban[p - 1] == GOAL || ban[p + 1] == GOAL || ban[p - xsize] == GOAL || ban[p + xsize] == GOAL){
return level;
}
}
}
}
}
boolean check(int p, int level){
if(ban[p] == level){
answer[p] = ROUTE;
if(search(p, level - 1)) return true;
answer[p] = BLANK;
}
return false;
}
boolean search(int p, int level){
if(level == 0){
disp(answer);
return AnswerType;
}
if(check(p - 1, level)) return true;
if(check(p + 1, level)) return true;
if(check(p - xsize, level)) return true;
if(check(p + xsize, level)) return true;
return false;
}
void disp(int[] ban){
int x, y, p;
p = 0;
for(y = 0; y < ysize; y++){
for(x = 0; x < xsize; x++){
switch(ban[p]){
case WALL : System.out.printf("*"); break;
case BLANK : System.out.printf(" "); break;
case START : System.out.printf("S"); break;
case GOAL : System.out.printf("G"); break;
default : System.out.printf("$"); break;
}
p++;
}
System.out.printf("\n");
}
}
}
