我一直在try 制作一个可以递归求解迷宫的程序(应该适用于任何迷宫).该算法的大部分递归都是有效的,但当迷宫判断死角和重新路由以找到解决方案(终点)的方法时,代码对其不起作用.我try 了多种调试方法,但都没有成功;我要么得到StackOverflowerrror,要么算法回溯一个位置.
Note "char indicators" for the 2D array:
- "*"=墙壁
- "#"=开始
- "$"=结束
- ''=可能的路径/不是墙
- "@"=路径
- "~"=死胡同
期望输出:
Presolved maze:
* * * * * * * * * *
* # * * * * * * * *
* * * *
* * * * *
* * * * *
* * * * * *
* * * * * *
* * * * *
* * * * * * * *
* $ *
* * * * * * * * * *
Maze solution:
* * * * * * * * * *
* # * * * * * * * *
* @ * @ @ @ @ @ * *
* @ * @ ~ ~ * @ * *
* @ @ @ * ~ * @ * *
* * * ~ ~ ~ * @ * *
* * ~ ~ * ~ * @ * *
* * ~ ~ * ~ * @ @ *
* * * * * * * ~ @ *
* ~ ~ ~ ~ ~ ~ ~ $ *
* * * * * * * * * *
Here is the code for the one that backtracks by only one position:
在这个版本中,我try 在找到一个可以回溯的位置后递归调用,并返回该位置以回溯并找到解决方案
import java.util.*;
public class mazeOG {
public static void main(String[] args) {
allocateMaze();
}
public static void allocateMaze() {
char[][] mazeArr = {{'*','*','*','*','*','*','*','*','*','*'},//0
{'*','#','*','*','*','*','*','*','*','*'},//1
{'*',' ','*',' ',' ',' ',' ',' ','*','*'},//2
{'*',' ','*',' ',' ',' ','*',' ','*','*'},//3
{'*',' ',' ',' ','*',' ','*',' ','*','*'},//4
{'*','*','*',' ',' ',' ','*',' ','*','*'},//5
{'*','*',' ',' ','*',' ','*',' ','*','*'},//6
{'*','*',' ',' ','*',' ','*',' ',' ','*'},//7
{'*','*','*','*','*','*','*',' ',' ','*'},//8
{'*',' ',' ',' ',' ',' ',' ',' ','$','*'},//9
{'*','*','*','*','*','*','*','*','*','*'}};//10
//setting row and col to 0 for display method
int row = 0;
int col = 0;
System.out.println("Presolved maze:");
displayMaze(mazeArr, row, col); //displays presolved maze
row = 1;
col = 1;
boolean isSolved = false;
System.out.println("\nMaze solution:");
algorithm(mazeArr, row, col, isSolved); //create variable for solved maze, sends maze allocation to method that solves the maze
System.out.println();
row = 0;
col = 0;
displayMaze(mazeArr, row, col); //displays traced + solved maze
}
public static void displayMaze(char[][] mazeArr, int row, int col) {
if (row < mazeArr.length) { //iterate through all (11) rows
if (col < mazeArr[row].length) { //iterate through all (11) columns
System.out.print(mazeArr[row][col] + " "); //displays the current index in the array
displayMaze(mazeArr, row, col+1); //repeats this method by iterating through the columns first
return;
}
System.out.println(); //enters the line after each row for display purposes
displayMaze(mazeArr, row+1, col=0); //repeats this method by iterating through the rows
}
}
public static char[][] algorithm(char[][] mazeArr, int row, int col, boolean isSolved){
boolean isPath = false; // assume there is no path
if (mazeArr[row][col] == '$' && isSolved == true) { // IF MAZE IS COMPLETELY SOLVED
return mazeArr;
} else { // IF MAZE IS NOT COMPLETELY SOLVED
// start searching thru the maze, assume there is no path
// THERE IS NO DEAD END
if (mazeArr[row - 1][col] == ' ') { // if north has a path
mazeArr[row - 1][col] = '@'; // block off path to not go back here again
isPath = true; // there is a path
isSolved = false; // assume maze is still not solved
return algorithm(mazeArr, --row, col, isSolved); // repeat process going to next north spot
}
if (mazeArr[row][col + 1] == ' ') { // if east has a path
mazeArr[row][col + 1] = '@'; // block off path to not go back here again
isPath = true; // there is a path
isSolved = false; // assume maze is still not solved
return algorithm(mazeArr, row, ++col, isSolved); // repeat process going to next east spot
}
if (mazeArr[row + 1][col] == ' ') { // if south has a path
mazeArr[row + 1][col] = '@'; // block off path to not go back here again
isPath = true; // there is a path
isSolved = false; // assume maze is still not solved
return algorithm(mazeArr, ++row, col, isSolved); // repeat process going to next south spot
}
if (mazeArr[row][col - 1] == ' ') { // if west has a path
mazeArr[row][col - 1] = '@'; // block off path to not go back here again
isPath = true; // there is a path
isSolved = false; // assume maze is still not solved
return algorithm(mazeArr, row, --col, isSolved); // repeat process going to next west spot
}
if (mazeArr[row][col] == '$') { // if you have reached the end of the maze
isSolved = true; // maze has been solved
return algorithm(mazeArr, row, col, isSolved); // algorithm will recognize
}
// finds alternate path if there's a dead end
if (mazeArr[row][col] != '#') {
mazeArr[row][col] = '~'; //indicates that this index is a dead end
}
if (isPath == false) {
if (mazeArr[row - 1][col] == '@' && mazeArr[row - 1][col] != '#') {// if north was a path
isPath = true;
isSolved = false;
return algorithm(mazeArr, --row, col, isSolved);//returns to initial position before hitting dead end
}
}
if (isPath == false) {
if (mazeArr[row - 1][col] == '@' && mazeArr[row][col+1] != '#') {// if east was a path
isPath = true;
isSolved = false;
return algorithm(mazeArr, row, ++col, isSolved);//returns to initial position before hitting dead end
}
}
if (isPath == false) {
if (mazeArr[row + 1][col] == '@' && mazeArr[row - 1][col] != '#') {// if south was a path
isPath = true;
isSolved = false;
return algorithm(mazeArr, ++row, col, isSolved);//returns to initial position before hitting dead end
}
}
if (isPath == false) {
if (mazeArr[row][col-1] == '@' && mazeArr[row - 1][col] != '#') {// if west was a path
isPath = true;
isSolved = false;
return algorithm(mazeArr, row, --col, isSolved);//returns to initial position before hitting dead end
}
}
if (isPath == false) { // if there's no way out, that means there is no solution
System.out.println("No Solution");
return mazeArr;
}
return mazeArr;
}
}
}
Output for this version:
Presolved maze:
* * * * * * * * * *
* # * * * * * * * *
* * * *
* * * * *
* * * * *
* * * * * *
* * * * * *
* * * * *
* * * * * * * *
* $ *
* * * * * * * * * *
Maze solution:
No Solution
* * * * * * * * * *
* # * * * * * * * *
* @ * @ @ @ @ @ * *
* @ * @ * @ * *
* @ @ @ * * @ * *
* * * * @ * *
* * * * @ * *
* * * * @ @ *
* * * * * * * @ @ *
* ~ @ @ @ @ @ @ $ *
* * * * * * * * * *
Here is the code for the version that gets StackOverflowError:
在这个版本中,我删除了代码中按位置追溯的部分并递归调用,相反,我只是指出该位置是一个死胡同,并递归调用算法来搜索下一个位置.
import java.util.*;
public class maze {
public static void main(String[] args) {
allocateMaze();
}
public static void allocateMaze() {
char[][] mazeArr = { { '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' }, // 0
{ '*', '#', '*', '*', '*', '*', '*', '*', '*', '*' }, // 1
{ '*', ' ', '*', ' ', ' ', ' ', ' ', ' ', '*', '*' }, // 2
{ '*', ' ', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 3
{ '*', ' ', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 4
{ '*', '*', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 5
{ '*', '*', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 6
{ '*', '*', ' ', ' ', '*', ' ', '*', ' ', ' ', '*' }, // 7
{ '*', '*', '*', '*', '*', '*', '*', ' ', ' ', '*' }, // 8
{ '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '$', '*' }, // 9
{ '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' } };// 10
// setting row and col to 0 for display method
int row = 0;
int col = 0;
System.out.println("Presolved maze:");
displayMaze(mazeArr, row, col); // displays presolved maze
row = 1;
col = 1;
boolean isSolved = false;
System.out.println("\nMaze solution:");
algorithm(mazeArr, row, col, isSolved); // create variable for solved maze, sends maze allocation to method that
// solves the maze
System.out.println();
row = 0;
col = 0;
displayMaze(mazeArr, row, col); // displays traced + solved maze
}
public static void displayMaze(char[][] mazeArr, int row, int col) {
if (row < mazeArr.length) { // iterate through all (11) rows
if (col < mazeArr[row].length) { // iterate through all (11) columns
System.out.print(mazeArr[row][col] + " "); // displays the current index in the array
displayMaze(mazeArr, row, col + 1); // repeats this method by iterating through the columns first
return;
}
System.out.println(); // enters the line after each row for display purposes
displayMaze(mazeArr, row + 1, col = 0); // repeats this method by iterating through the rows
}
}
public static char[][] algorithm(char[][] mazeArr, int row, int col, boolean isSolved) {
boolean isPath = false; // assume there is no path
if (mazeArr[row][col] == '$' && isSolved == true) { // IF MAZE IS COMPLETELY SOLVED
return mazeArr;
} else { // IF MAZE IS NOT COMPLETELY SOLVED
// start searching thru the maze,
// assume there is no path
// THERE IS NO DEAD END
if (mazeArr[row - 1][col] == ' ') { // if north has a path
mazeArr[row - 1][col] = '@'; // block off path to not go back here again
isPath = true; // there is a path
isSolved = false; // assume maze is still not solved
return algorithm(mazeArr, --row, col, isSolved); // repeat process going to next north spot
}
if (mazeArr[row][col + 1] == ' ') { // if east has a path
mazeArr[row][col + 1] = '@'; // block off path to not go back here again
isPath = true; // there is a path
isSolved = false; // assume maze is still not solved
return algorithm(mazeArr, row, ++col, isSolved); // repeat process going to next east spot
}
if (mazeArr[row + 1][col] == ' ') { // if south has a path
mazeArr[row + 1][col] = '@'; // block off path to not go back here again
isPath = true; // there is a path
isSolved = false; // assume maze is still not solved
return algorithm(mazeArr, ++row, col, isSolved); // repeat process going to next south spot
}
if (mazeArr[row][col - 1] == ' ') { // if west has a path
mazeArr[row][col - 1] = '@'; // block off path to not go back here again
isPath = true; // there is a path
isSolved = false; // assume maze is still not solved
return algorithm(mazeArr, row, --col, isSolved); // repeat process going to next west spot
}
if (mazeArr[row][col] == '$') { // if you have reached the end of the maze
isSolved = true; // maze has been solved
return algorithm(mazeArr, row, col, isSolved); // algorithm will recognize
}
//code from here and below is for the case of a dead end
if (mazeArr[row][col] != '#' && isPath == false) {
mazeArr[row][col] = '~'; // indicates that this index is a dead end
isPath = true;
isSolved = false;
return algorithm(mazeArr, row, col, isSolved);
}
if (isPath == false) { // if there's no way out, that means there is no solution
System.out.println("No Solution");
return mazeArr;
}
return mazeArr;
}
}
}
任何帮助都会非常好!谢谢:)
编辑:
public static void main(String[] args) {
int row = 0, col = 0;
char[][] mazeArr = { { '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' }, // 0
{ '*', '#', '*', '*', '*', '*', '*', '*', '*', '*' }, // 1
{ '*', ' ', '*', ' ', ' ', ' ', ' ', ' ', '*', '*' }, // 2
{ '*', ' ', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 3
{ '*', ' ', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 4
{ '*', '*', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 5
{ '*', '*', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 6
{ '*', '*', ' ', ' ', '*', ' ', '*', ' ', ' ', '*' }, // 7
{ '*', '*', '*', '*', '*', '*', '*', ' ', ' ', '*' }, // 8
{ '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '$', '*' }, // 9
{ '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' } };// 10
System.out.println("Input maze:");
displayMaze(mazeArr, row, col);
System.out.println("\nMaze solution:");
boolean isSolved = algorithm(mazeArr);
if (isSolved) {
displayMaze(mazeArr, row, col);
} else {
System.out.println("No Solution");
}
}
public static void displayMaze(char[][] mazeArr, int row, int col) {
if (row < mazeArr.length) { //iterate through all (11) rows
if (col < mazeArr[row].length) { //iterate through all (11) columns
//displays maze without dead end indicators
if(mazeArr[row][col] == '~') {
//mazeArr[row][col] = ' ';
}
System.out.print(mazeArr[row][col] + " "); //displays the current index in the array
displayMaze(mazeArr, row, col+1); //repeats this method by iterating through the columns first
return;
}
System.out.println(); //enters the line after each row for display purposes
displayMaze(mazeArr, row+1, col=0); //repeats this method by iterating through the rows
}
}
//indicates starting point for the maze to start solving and recursively calls algorithm method that is overloaded
//pre: char 2D array mazeArr
//post: returns a boolean value from the overloaded algorithm method
public static boolean algorithm(char[][] mazeArr) {
int row = 1, col = 1; // where maze starts
return algorithm(mazeArr, row, col);
}
//solves the maze looking for a solution (if there is one), modifies the 2D array accordingly
//to the algorithm to trace the solution
//pre: char 2D array mazeArr, int row and col
//post: returns boolean value depending on the algorithms solution
public static boolean algorithm(char[][] mazeArr, int row, int col) {
if (mazeArr[row][col] == '$') { // found the target/exit
return true; //maze is completely solved
}
if (mazeArr[row][col] == ' ') { // if there is a path
mazeArr[row][col] = '@'; //mark as visited, block off path to not go back here again
}
else if (mazeArr[row][col] != '#') { // not allowed
return false;
}
// the core of the algorithm: try each direction until true is returned
if (algorithm(mazeArr, row, col - 1) // west
|| algorithm(mazeArr, row - 1, col) // north
|| algorithm(mazeArr, row, col + 1) // east
|| algorithm(mazeArr, row + 1, col) // south
) {
return true; // path found
}
if (mazeArr[row][col] == '@') { // mark backtracking
mazeArr[row][col] = '~'; // indicates that this index is a dead end
}
return false;
}