二维迷宫的递归算法？

（这不是重复）我们在所有4个侧面都有一个由X围绕的2D迷宫，也有内部块。
迷宫的所有这些字符都存储在2D数组中。 程序必须找到从’S’开始到目标’G’的路径。 为此，使用名为’solve（int row，int col）的布尔方法，并使用’S’的行和列索引进行初始化。 算法必须是递归的。 如果它能够找到’G’的路径并且其他方面是假的，那么它应该返回true。 这是我试图解决这个显示“部分正确结果”的问题的方法。

public boolean solve(int row, int col) { char right = this.theMaze[row][col + 1]; char left = this.theMaze[row][col - 1]; char up = this.theMaze[row - 1][col]; char down = this.theMaze[row + 1][col]; if (right == 'G' || left == 'G' || up == 'G' || down == 'G') { return true; } System.out.println("position=>"+"("+row + ":" + col+")"); if (right == ' ') { return solve(row,col+1); } if (down == ' ') { return solve(row+1,col); } if (left == ' ') { return solve(row,col-1); } if (up == ' ') { return solve(row-1,col); } return false; } 

这是它解决的输出：

  0 1 2 3 4 5 6 7 8 9 10 0 XXXXXXXXXXX 1 XXSXXXXXXX 2 XXXXXXXXX 3 XXXXXXXXX 4 XXXXXXXXX 5 XXXXXXXXX 6 XXXXXXXXX 7 XXXXXXXGXX 8 XXXX 9 XXXXXXXXXXX position=>(1:2) position=>(2:2) position=>(3:2) position=>(4:2) position=>(5:2) position=>(6:2) position=>(7:2) position=>(8:2) position=>(8:3) position=>(8:4) position=>(8:5) position=>(8:6) position=>(8:7) true 

但是当我把’G’放一步（6,8）时。 它显示stackOverflow错误。 原因是因为递归发生在这个状态的2个点之间（不知何故就像间接递归一样）。

我怎么解决这个问题。 反正有没有告诉程序向上移动而不是向下移动？ 改变条件语句的位置不会起作用。 并且考虑一个有多条路径的位置，但只有一条通向“G”。 如何回到初始位置并尝试其他路径？ 提前致谢。

更新：

这是一个Github Repo链接到我这个问题的完整解决方案。

Answer 1

您可以在已经介入的空间中填写备用符号，这样您的程序就会知道它已经存在。

Answer 2

在您目前的代码中，您可能会在不查看其他连接位置的情况下返回false 。

在从if条件返回之前，您应该查看其他可能性。
此外，您应检查是否已访问该位置以避免无限递归。

将您的代码更改为：

 bool solved = false; visited[row][col] = true; if (right == ' ' && !visited[row][col+1]) { solved = solve(row,col+1); } if (down == ' ' && !solved && !visited[row+1][col]) { solved = solve(row+1,col); } if (left == ' ' && !solved && !visited[row][col-1]) { solved = solve(row,col-1); } if (up == ' ' && !solved !visited[row-1][col]) { solved = solve(row-1,col); } return solved; 

Answer 3

您可以使用DFS或BFS。 DFS是最简单的。 您只需进行递归，在所有4/8方向导航并将该位置（X，Y）标记为已访问。 如果这是你的命运’G’，则返回true，否则继续。

提示：

• 不要使用相同的矩阵来阅读地图并将其标记为已访问，KISS
• 你必须经常检查你是否发现了G.你可以通过返回FALSE或TRUE来做到这一点，或者你可以使用全局变量。

如果您在实施时遇到问题，请尝试谷歌搜索一些有关此问题的源代码： http ： //en.wikipedia.org/wiki/Flood_fill

http://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/

Answer 4

这是一个伪代码，您可以解决迷宫问题并回溯解决方案： –

 boolean Solve(int x,int y) { if(isTarget(x,y)) return(true) if(valid(x+1,y)&&Map[x+1][y]==' ') { Map[x][y] = 'D' if(Solve(x+1,y)) return(true) Map[x][y] = ' ' } if(valid(x-1,y)&&Map[x-1][y]==' ') { Map[x][y] = 'U' if(Solve(x-1,y)) return(true) Map[x][y] = ' ' } if(valid(x,y+1)&&Map[x][y+1]==' ') { Map[x][y] = 'R' if(Solve(x,y+1)) return(true) Map[x][y] = ' ' } if(valid(x,y-1)&&Map[x][y-1]==' ') { Map[x][y] = 'L' if(Solve(x,y-1)) return(true) Map[x][y] = ' ' } return(false); } 

Answer 5

如果您正在寻找完整的解决方案，我已将其上传到我的Github存储库中 。

Answer 6

灵感来自于本文解决2D迷宫 ，一种递归解决方案

 const CORRIDOR = 0; const WALL = 1; const EXIT = 2; // board - 2D array // start - [row, column] location of start point function findPath(board, start) { let seenPath = new Set(); findPathRecur(board, start, seenPath) return Array.from(seenPath); } function findPathRecur(board, point, seenPath) { let row = point[0], column = point[1]; // Base Case if (!isValidPathPoint(board, point, seenPath)) { return false; } if (board[row][column] === EXIT) { seenPath.add(point.toString()); return true; } // console.log("Curr -", point, ", Seen -", Array.from(seenPath)); seenPath.add(point.toString()); let leftColumn = [row, column - 1], rightColumn = [row, column + 1], topRow = [row - 1, column], bottomRow = [row + 1, column]; if (findPathRecur(board, leftColumn, seenPath)) { return true; } if (findPathRecur(board, rightColumn, seenPath)) { return true; } if (findPathRecur(board, topRow, seenPath)) { return true; } if (findPathRecur(board, bottomRow, seenPath)) { return true; } seenPath.delete(point.toString()); return false; } // Check if the point is on valid path function isValidPathPoint(board, point, seenPath) { let row = point[0]; let column = point[1]; // Check if point exists if (board[row] != null && board[row][column] != null) { // To avoid cycle if (!seenPath.has(point.toString())) { // Not a Wall if (board[row][column] !== WALL) { return true; } } } return false; } // Test Program let maze = [ [1, 1, 1], [0, 0, 1], [1, 2, 1] ]; let testStart = [ [1,0], [1,1], [2,1], [0,0], [5,5] ]; testStart.forEach(function(start, i) { console.log("Test Case:",i); console.log("\tStart -", start, "Path -", findPath(maze, start)); })