行和列迷宫递归误差

我得到了包含建立一个迷宫所需的所有代码。我的工作是编写用于解决迷宫问题的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
和50.makeMove(row + 1, col); //to move down。

有我在这两个做了一个逻辑上的错误？

来源

2013-11-20 user2745043

你应该随身携带迷宫的当前状态makeMove方法的参数。在你的情况下迷宫的状态是访问矩阵。

来源

2013-11-20 20:54:11 Amine

通过你得到的错误判断，在算法的“无限循环”的代码结果自称一遍又一遍不正确终用完的调用堆栈空间之前。请注意，这并不意味着堆栈跟踪指示的行是错误的真正原因 - 这是程序空间不足的地方，但实际的错误逻辑通常是其他地方。

一两件事是肯定引起麻烦的是这样的：

boolean[][]visited = new boolean[MAX_ROWS][MAX_COLS];

这将创建布尔的一个新的二维阵列（或者更准确地说，boolean型数组的数组）的递归的每一步，并将其初始化false（因为这是Java中布尔值的默认值）。其结果是，你的算法将继续访问过它已经访问了，因为每个递归步骤都有自己的阵列片，充满了false这标志着每个瓦片仍然未访问过。通过将数组作为参数传递给每个递归调用，或者将其存储在函数之外，可以解决此特定问题。

来源

2013-11-20 20:54:18 kviiri

boolean[][]visited = new boolean[MAX_ROWS][MAX_COLS];

为每个递归调用生成上述状态不存储状态值。最好把它作为一个全局变量或者作为参数传递。

来源

2013-12-10 02:10:45

行和列迷宫递归误差

回答

相关问题