我得到的代码包含了构建迷宫所需的一切。我的工作是编写用于解决迷宫的makeMove
方法。这就是我目前所拥有的:
protected void makeMove( int row, int col )
{
int MAX_ROWS = maze.length;
int MAX_COLS = maze.length;
boolean found = false;
boolean[][]visited = new boolean[MAX_ROWS][MAX_COLS];
//visited[startRow][startCol] = true;
if (row < 0 || row >= MAX_ROWS || col < 0 || col >= MAX_COLS || visited[row][col] || maze[row][col] == 1)
return;
visited[row][col] = true;
found = row == endRow && col == endCol;
/*if(row == endRow && col == endCol) {
found = true;
}*/
if(!found && maze[row][col - 1]!=1 && !visited[row][col]) { // move left
makeMove(row, col -1);
visited[row][col -1] = true;
}
if(!found && maze[row - 1][col]!=1 && !visited[row-1][col]) { // move up
makeMove(row-1, col);
visited[row-1][col] = true;
}
if(!found && maze[row][col + 1]!=1 && !visited[row][col + 1]) { // move right
makeMove(row, col + 1);
visited[row][col + 1] = true;
}
if(!found && maze[row + 1][col]!=1 && !visited[row + 1][col]) { // move down
makeMove(row + 1, col);
visited[row + 1][col] = true;
}
当在一个有8行8列的迷宫中这样运行时,我总是会出现堆栈溢出错误。
我相信错误显示它在第42行和第50行,这将是42. MakeMove(row-1, col); //to move up
和CCD_ 3。
我在这两个方面犯了逻辑错误吗?
您应该将迷宫的当前状态作为makeMove方法的参数。在您的案例中,迷宫的状态是访问矩阵。
根据您得到的错误判断,您的代码会导致算法一次又一次地调用自己,而不会在调用堆栈中的空间用完之前正确终止。请注意,这并不意味着堆栈跟踪指示的行是错误的实际原因——它是程序空间不足的地方,但实际的错误逻辑通常在其他地方。
有一件事肯定会引起麻烦:
boolean[][]visited = new boolean[MAX_ROWS][MAX_COLS];
这为递归的每个步骤创建了一个新的布尔值2D数组(或者准确地说,布尔值数组),并将其初始化为false
(因为这是Java中布尔值的默认值)。因此,您的算法将继续访问它已经访问过的瓦片,因为每个递归步骤都有自己的数组,其中充满了false
,表示每个瓦片仍然未被访问。这个特殊的问题可以通过在每次递归调用时将数组作为参数传递,或者将其存储在函数之外来解决。
boolean[][]visited = new boolean[MAX_ROWS][MAX_COLS];
为每个递归调用生成上述状态并不存储状态值。最好将其保留为全局变量或作为参数传递。