首页 文章

使用递归的迷宫求解器

提问于
浏览 次
0

我得到了一些构建迷宫的代码和其他所需的代码，抽象的迷宫类包含一个抽象方法'makeMove（int row，int col）'这是我试图写的方法来解决迷宫，向左移动，正确，向上，向下

我刚开始研究这个问题，下面就是我到目前为止所做的一切 .

int MAX_ROWS = endRow + 1;
int MAX_COLS = endCol + 1;
boolean[][]visited = new boolean[MAX_ROWS][MAX_COLS];
protected void makeMove( int row, int col )
{
    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 (!found) {
        makeMove(row, col - 1);
        makeMove(row, col + 1);
        makeMove(row - 1, col);
        makeMove(row + 1, col);
    }

    }
    /*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;
    }*/

好的，我有代码工作到我不再收到错误的地方 .

感谢您的帮助 .

java recursion maze

1 回答

  • 1
    boolean[][] visited = null;

    声明一个局部变量 . 您需要将其声明为类的成员，以便它可以在 makeMove 的调用之间保持不变 . 您还需要正确初始化它：

    boolean[][] visited = new boolean[...][...];

    您还需要执行边界检查 . 在几次递归调用之后，你将到达迷宫的边缘并超出阵列的范围 .

    因此代码可能如下所示：

    int MAX_ROWS = ...
int MAX_COLS = ...

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

protected void makeMove(int row, int col) {
    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 (!found) {
        makeMove(row, col - 1);
        makeMove(row, col + 1);
        makeMove(row - 1, col);
        makeMove(row + 1, col);
    }
}

    其中 MAX_ROWS 和 MAX_COLS 对应于迷宫的尺寸 . 请注意，默认情况下 visited 初始化为 false . 如果要在不同的迷宫上多次调用此方法，则应将其包装在将重新初始化 visited 的方法中 .

    回复于

相关问题