迷宫 2D 递归算法死胡同问题
Maze 2D Recursive Algorithm Dead End Issue
我一直在尝试制作一个可以递归解决迷宫的程序（应该适用于任何迷宫）。该算法的大部分递归都有效，但是当迷宫检查死胡同和重新路由以找到解决方案（终点）的方法时，代码对其不起作用。我已经尝试了多种调试方法，但并没有让我走得太远；我要么得到 WhosebugError，要么算法工作回溯一个位置。
注意二维数组的“字符指示符”：
- '*' = 墙壁
- '#' = 开始
- '$' = 结束
- ' '=可能path/not一堵墙
- '@' = 路径
- '~' = 死胡同
期望的输出：
Presolved maze:
* * * * * * * * * *
* # * * * * * * * *
* * * *
* * * * *
* * * * *
* * * * * *
* * * * * *
* * * * *
* * * * * * * *
* $ *
* * * * * * * * * *
Maze solution:
* * * * * * * * * *
* # * * * * * * * *
* @ * @ @ @ @ @ * *
* @ * @ ~ ~ * @ * *
* @ @ @ * ~ * @ * *
* * * ~ ~ ~ * @ * *
* * ~ ~ * ~ * @ * *
* * ~ ~ * ~ * @ @ *
* * * * * * * ~ @ *
* ~ ~ ~ ~ ~ ~ ~ $ *
* * * * * * * * * *
这里是只回溯一个位置的代码：
在这个版本中，我在找到可以回溯的位置并返回该位置以回溯并找到解决方案后尝试递归调用
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;
}
}
}
此版本的输出：
Presolved maze:
* * * * * * * * * *
* # * * * * * * * *
* * * *
* * * * *
* * * * *
* * * * * *
* * * * * *
* * * * *
* * * * * * * *
* $ *
* * * * * * * * * *
Maze solution:
No Solution
* * * * * * * * * *
* # * * * * * * * *
* @ * @ @ @ @ @ * *
* @ * @ * @ * *
* @ @ @ * * @ * *
* * * * @ * *
* * * * @ * *
* * * * @ @ *
* * * * * * * @ @ *
* ~ @ @ @ @ @ @ $ *
* * * * * * * * * *
这是获取 WhosebugError 的版本的代码：
在这个版本中，我删除了代码中按位置回溯并递归调用的部分，而是仅指示该位置是死胡同并递归调用算法来搜索下一个位置.
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;
}
有几个问题，包括：
死胡同不应触发新的递归调用。当从递归回溯时应该发生死端标记，并且应该向调用者表明没有成功。
每个检查特定方向（北，...等）的 if 语句将在其块中执行 return，这意味着如果有这样的一个方向none其他方向都会尝试
由于递归调用不return是否成功，调用者无法知道是否应该从另一个方向尝试
不是问题，但是：
- 还有一些代码重复，你应该避免。
- 没有充分的理由使显示函数递归。只需使用两个
for 循环 遍历单元格
- 避免在你的主程序中使用
row 和 col 变量：它们在那里应该没有用处。
- 当你改变迷宫时，应该没有必要也return那个迷宫。呼叫者将在呼叫后以任何方式访问填充的迷宫。
- 当您将 起点 (
#) 的搜索与算法的其余部分分开时，代码会更简单。
函数成功的关键之一是 return 是一个布尔值，指示是否找到路径。这样算法就可以决定是否应该在另一个方向再试一次。
这里是你的代码的修改：
import java.util.*;
public class Main {
public static void main(String[] args) {
char[][] mazeArr = {
{ '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' }, // 0
{ '*', '#', '*', '*', '*', '*', '*', '*', '*', '*' }, // 1
{ '*', ' ', '*', ' ', ' ', ' ', ' ', ' ', '*', '*' }, // 2
{ '*', ' ', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 3
{ '*', ' ', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 4
{ '*', '*', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 5
{ '*', '*', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 6
{ '*', '*', ' ', ' ', '*', ' ', '*', ' ', ' ', '*' }, // 7
{ '*', '*', '*', '*', '*', '*', '*', ' ', ' ', '*' }, // 8
{ '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '$', '*' }, // 9
{ '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' } };// 10
System.out.println("Input maze:");
displayMaze(mazeArr);
System.out.println("\nMaze solution:");
boolean isSolved = algorithm(mazeArr);
if (isSolved) {
displayMaze(mazeArr);
} else {
System.out.println("No Solution");
}
}
public static void displayMaze(char[][] mazeArr) {
for (char[] row : mazeArr) {
for (char cell : row) {
System.out.print(cell + " ");
}
System.out.println();
}
}
public static boolean algorithm(char[][] mazeArr) {
// Look for starting point
for (int row = 0; row < mazeArr.length; row++) {
for (int col = 0; col < mazeArr[0].length; col++) {
if (mazeArr[row][col] == '#') {
return algorithm(mazeArr, row, col);
}
}
}
return false; // No starting point found
}
public static boolean algorithm(char[][] mazeArr, int row, int col) {
if (mazeArr[row][col] == '$') { // Found the target
return true;
}
if (mazeArr[row][col] == ' ') {
mazeArr[row][col] = '@'; // Mark as visited
} 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] = '~';
}
return false;
}
}
没有循环
从评论中我了解到您不想使用循环。在这种情况下，使用递归在单独的递归函数中查找起始单元格，并且 return 找到的点作为单个整数 (row*width + col).
对应代码如下：
public class Main {
public static void main(String[] args) {
char[][] mazeArr = {
{ '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' }, // 0
{ '*', '#', '*', '*', '*', '*', '*', '*', '*', '*' }, // 1
{ '*', ' ', '*', ' ', ' ', ' ', ' ', ' ', '*', '*' }, // 2
{ '*', ' ', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 3
{ '*', ' ', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 4
{ '*', '*', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 5
{ '*', '*', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 6
{ '*', '*', ' ', ' ', '*', ' ', '*', ' ', ' ', '*' }, // 7
{ '*', '*', '*', '*', '*', '*', '*', ' ', ' ', '*' }, // 8
{ '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '$', '*' }, // 9
{ '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' } };// 10
System.out.println("Input maze:");
displayMaze(mazeArr);
System.out.println("\nMaze solution:");
boolean isSolved = algorithm(mazeArr);
if (isSolved) {
displayMaze(mazeArr);
} else {
System.out.println("No Solution");
}
}
public static void displayMaze(char[][] mazeArr) {
displayMaze(mazeArr, 0, 0); // add the arguments
}
public static void displayMaze(char[][] mazeArr, int row, int col) {
if (row >= mazeArr.length) {
return; // all done
}
if (col >= mazeArr[0].length) {
System.out.println();
displayMaze(mazeArr, row + 1, 0);
} else {
System.out.print(mazeArr[row][col] + " ");
displayMaze(mazeArr, row, col + 1);
}
}
public static int findStart(char[][] mazeArr, int i) {
// Look for starting point. i is combination of row/col
int row = i / mazeArr.length;
if (row >= mazeArr.length) {
return -1; // all done, and not found
}
int col = i % mazeArr[0].length;
if (mazeArr[row][col] == '#') {
return i; // found it
}
return findStart(mazeArr, i + 1);
}
public static boolean algorithm(char[][] mazeArr) {
int i = findStart(mazeArr, 0);
if (i == -1) {
return false; // No starting point found
}
int row = i / mazeArr.length;
int col = i % mazeArr[0].length;
return algorithm(mazeArr, row, col);
}
public static boolean algorithm(char[][] mazeArr, int row, int col) {
if (mazeArr[row][col] == '$') { // Found the target
return true;
}
if (mazeArr[row][col] == ' ') {
mazeArr[row][col] = '@'; // Mark as visited
} 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] = '~';
}
return false;
}
}
我一直在尝试制作一个可以递归解决迷宫的程序（应该适用于任何迷宫）。该算法的大部分递归都有效，但是当迷宫检查死胡同和重新路由以找到解决方案（终点）的方法时，代码对其不起作用。我已经尝试了多种调试方法，但并没有让我走得太远；我要么得到 WhosebugError，要么算法工作回溯一个位置。
注意二维数组的“字符指示符”：
- '*' = 墙壁
- '#' = 开始
- '$' = 结束
- ' '=可能path/not一堵墙
- '@' = 路径
- '~' = 死胡同
期望的输出：
Presolved maze:
* * * * * * * * * *
* # * * * * * * * *
* * * *
* * * * *
* * * * *
* * * * * *
* * * * * *
* * * * *
* * * * * * * *
* $ *
* * * * * * * * * *
Maze solution:
* * * * * * * * * *
* # * * * * * * * *
* @ * @ @ @ @ @ * *
* @ * @ ~ ~ * @ * *
* @ @ @ * ~ * @ * *
* * * ~ ~ ~ * @ * *
* * ~ ~ * ~ * @ * *
* * ~ ~ * ~ * @ @ *
* * * * * * * ~ @ *
* ~ ~ ~ ~ ~ ~ ~ $ *
* * * * * * * * * *
这里是只回溯一个位置的代码：
在这个版本中，我在找到可以回溯的位置并返回该位置以回溯并找到解决方案后尝试递归调用
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;
}
}
}
此版本的输出：
Presolved maze:
* * * * * * * * * *
* # * * * * * * * *
* * * *
* * * * *
* * * * *
* * * * * *
* * * * * *
* * * * *
* * * * * * * *
* $ *
* * * * * * * * * *
Maze solution:
No Solution
* * * * * * * * * *
* # * * * * * * * *
* @ * @ @ @ @ @ * *
* @ * @ * @ * *
* @ @ @ * * @ * *
* * * * @ * *
* * * * @ * *
* * * * @ @ *
* * * * * * * @ @ *
* ~ @ @ @ @ @ @ $ *
* * * * * * * * * *
这是获取 WhosebugError 的版本的代码：
在这个版本中，我删除了代码中按位置回溯并递归调用的部分，而是仅指示该位置是死胡同并递归调用算法来搜索下一个位置.
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;
}
有几个问题，包括：
死胡同不应触发新的递归调用。当从递归回溯时应该发生死端标记，并且应该向调用者表明没有成功。
每个检查特定方向（北，...等）的
if语句将在其块中执行return，这意味着如果有这样的一个方向none其他方向都会尝试由于递归调用不return是否成功，调用者无法知道是否应该从另一个方向尝试
不是问题，但是：
- 还有一些代码重复，你应该避免。
- 没有充分的理由使显示函数递归。只需使用两个
for循环 遍历单元格
- 避免在你的主程序中使用
row和col变量：它们在那里应该没有用处。 - 当你改变迷宫时，应该没有必要也return那个迷宫。呼叫者将在呼叫后以任何方式访问填充的迷宫。
- 当您将 起点 (
#) 的搜索与算法的其余部分分开时，代码会更简单。
函数成功的关键之一是 return 是一个布尔值，指示是否找到路径。这样算法就可以决定是否应该在另一个方向再试一次。
这里是你的代码的修改：
import java.util.*;
public class Main {
public static void main(String[] args) {
char[][] mazeArr = {
{ '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' }, // 0
{ '*', '#', '*', '*', '*', '*', '*', '*', '*', '*' }, // 1
{ '*', ' ', '*', ' ', ' ', ' ', ' ', ' ', '*', '*' }, // 2
{ '*', ' ', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 3
{ '*', ' ', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 4
{ '*', '*', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 5
{ '*', '*', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 6
{ '*', '*', ' ', ' ', '*', ' ', '*', ' ', ' ', '*' }, // 7
{ '*', '*', '*', '*', '*', '*', '*', ' ', ' ', '*' }, // 8
{ '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '$', '*' }, // 9
{ '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' } };// 10
System.out.println("Input maze:");
displayMaze(mazeArr);
System.out.println("\nMaze solution:");
boolean isSolved = algorithm(mazeArr);
if (isSolved) {
displayMaze(mazeArr);
} else {
System.out.println("No Solution");
}
}
public static void displayMaze(char[][] mazeArr) {
for (char[] row : mazeArr) {
for (char cell : row) {
System.out.print(cell + " ");
}
System.out.println();
}
}
public static boolean algorithm(char[][] mazeArr) {
// Look for starting point
for (int row = 0; row < mazeArr.length; row++) {
for (int col = 0; col < mazeArr[0].length; col++) {
if (mazeArr[row][col] == '#') {
return algorithm(mazeArr, row, col);
}
}
}
return false; // No starting point found
}
public static boolean algorithm(char[][] mazeArr, int row, int col) {
if (mazeArr[row][col] == '$') { // Found the target
return true;
}
if (mazeArr[row][col] == ' ') {
mazeArr[row][col] = '@'; // Mark as visited
} 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] = '~';
}
return false;
}
}
没有循环
从评论中我了解到您不想使用循环。在这种情况下，使用递归在单独的递归函数中查找起始单元格，并且 return 找到的点作为单个整数 (row*width + col).
对应代码如下：
public class Main {
public static void main(String[] args) {
char[][] mazeArr = {
{ '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' }, // 0
{ '*', '#', '*', '*', '*', '*', '*', '*', '*', '*' }, // 1
{ '*', ' ', '*', ' ', ' ', ' ', ' ', ' ', '*', '*' }, // 2
{ '*', ' ', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 3
{ '*', ' ', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 4
{ '*', '*', '*', ' ', ' ', ' ', '*', ' ', '*', '*' }, // 5
{ '*', '*', ' ', ' ', '*', ' ', '*', ' ', '*', '*' }, // 6
{ '*', '*', ' ', ' ', '*', ' ', '*', ' ', ' ', '*' }, // 7
{ '*', '*', '*', '*', '*', '*', '*', ' ', ' ', '*' }, // 8
{ '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '$', '*' }, // 9
{ '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' } };// 10
System.out.println("Input maze:");
displayMaze(mazeArr);
System.out.println("\nMaze solution:");
boolean isSolved = algorithm(mazeArr);
if (isSolved) {
displayMaze(mazeArr);
} else {
System.out.println("No Solution");
}
}
public static void displayMaze(char[][] mazeArr) {
displayMaze(mazeArr, 0, 0); // add the arguments
}
public static void displayMaze(char[][] mazeArr, int row, int col) {
if (row >= mazeArr.length) {
return; // all done
}
if (col >= mazeArr[0].length) {
System.out.println();
displayMaze(mazeArr, row + 1, 0);
} else {
System.out.print(mazeArr[row][col] + " ");
displayMaze(mazeArr, row, col + 1);
}
}
public static int findStart(char[][] mazeArr, int i) {
// Look for starting point. i is combination of row/col
int row = i / mazeArr.length;
if (row >= mazeArr.length) {
return -1; // all done, and not found
}
int col = i % mazeArr[0].length;
if (mazeArr[row][col] == '#') {
return i; // found it
}
return findStart(mazeArr, i + 1);
}
public static boolean algorithm(char[][] mazeArr) {
int i = findStart(mazeArr, 0);
if (i == -1) {
return false; // No starting point found
}
int row = i / mazeArr.length;
int col = i % mazeArr[0].length;
return algorithm(mazeArr, row, col);
}
public static boolean algorithm(char[][] mazeArr, int row, int col) {
if (mazeArr[row][col] == '$') { // Found the target
return true;
}
if (mazeArr[row][col] == ' ') {
mazeArr[row][col] = '@'; // Mark as visited
} 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] = '~';
}
return false;
}
}