我一直在尝试编写一个可以递归解决迷宫的程序。但我的算法方法中的递归存在问题。该算法只能求解一个位置的解。
这是控制台上的:
注意二维数组的“字符指示符”:
- '*' = 墙壁
- '#' = 开始
- '$' = 结束
- ' ' = 可能的路径/不是墙壁
- '@' = 路径
- '~' = 死胡同
期望的输出:
Presolved maze:
* * * * * * * * * *
* # * * * * * * * *
* * * *
* * * * *
* * * * *
* * * * * *
* * * * * *
* * * * *
* * * * * * * *
* $ *
* * * * * * * * * *
Maze solution:
* * * * * * * * * *
* # * * * * * * * *
* @ * @ @ @ @ @ * *
* @ * @ ~ ~ * @ * *
* @ @ @ * ~ * @ * *
* * * ~ ~ ~ * @ * *
* * ~ ~ * ~ * @ * *
* * ~ ~ * ~ * @ ~ *
* * * * * * * @ ~ *
* ~ ~ ~ ~ ~ ~ @ $ *
* * * * * * * * * *
我得到的输出:
Presolved maze:
* * * * * * * * * *
* # * * * * * * * *
* * * *
* * * * *
* * * * *
* * * * * *
* * * * * *
* * * * *
* * * * * * * *
* $ *
* * * * * * * * * *
Maze solution:
* * * * * * * * * *
* # * * * * * * * *
* @ * * *
* * * * *
* * * * *
* * * * * *
* * * * * *
* * * * *
* * * * * * * *
* $ *
* * * * * * * * * *
我尝试过其他解决方案，例如在一般情况下删除递归中的递归，但这只是回归了我的算法可以做的微小进展(即找到一个位置)。我想知道我还能做些什么来解决这个问题？其他方法有效，但方法“算法”并不像我希望的那样工作。
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
if (isSolved == false && isPath == false) { // 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
}
} else { // 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][col+1] == '@' && 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][col-1] != '#') { // if west was a path
isPath = true;
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;
}
}
}
最佳答案
您需要输入 ++或--之前row或col当您记忆时 algorithm() 。当其中之一出现在变量之后时，变量会递增，但不会出现值:
public class Test {
public static void main(String[] args) {
int x = 5;
int y = x++;
System.out.println(x + " " + y);
}
}
给出
6 5
以上x++递增x ，但是y设置为值 x前。要解决此问题，请将增量放在变量之前，例如 ++row :
public class Test {
public static void main(String[] args) {
int x = 5;
int y = ++x;
System.out.println(x + " " + y);
}
}
输出:
6 6
关于java - 迷宫 2D 递归算法问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/71814048/