迷宫回溯水平移动

Question

[在迷宫运动中的老鼠水平移动时，我遇到了一个问题。我将老鼠定义为首先走下去（如果有的话），然后向右然后向左。问题是，当它走到一条死胡同的路径上并试图找到怀特路径时，老鼠会混淆右边和左边。路径存储在数组中。出口在底部的任何地方。老鼠可以向任何方向移动。 （0,3）是开始。

0 =免费通过

1 =已阻止

请参见以下示例：

1 1 1 0 1 1 1
1 1 1 0 1 1 1
1 0 0 0 1 0 1
1 0 1 0 1 0 0
1 1 1 0 1 1 1
1 0 0 0 0 0 1
1 0 1 1 1 0 1
0 0 1 1 1 0 1
0 1 1 1 0 1 1

路径：（0,3）（1,3）（2,3）（3,3）（4,3）（5,3）（5,4）（5,5）（6,5）（ 7,5）（6,5）（5,5）（5,4）（5,5）（6,5）（7,5）（6,5）（5,5）（5,4）（ 5,5）...

在此示例中，位于（5,4）的老鼠没有选择向左移动，而是循环了前一条路径。我真的在试图找到解决方案。有人知道吗？

这是我的一些代码：

public boolean solveRatMaze(int maze[][], int x, int y, int sol[][], Stack stack) {
        if ((x == maze.length-1 && isValidPlace(maze, x, y)) { //when (x,y) is the bottom right room
            sol[x][y] = 0;
            stack.push(String.valueOf(x));
            stack.push(String.valueOf(y));
            return true;
        }
        if(isValidPlace(maze, x, y) == true) {     //check whether (x,y) is valid or not
            sol[x][y] = 0; //set 0, when it is valid place
            if (solveRatMaze(maze,x+1, y, sol, stack) == true)       //when x direction is blocked, go for bottom direction
                return true;    //when x direction is blocked, go for bottom direction
            if (solveRatMaze(maze, x, y + 1, sol, stack) == true)         //find path by moving right direction
                return true;     //when x direction is blocked, go for bottom direction
            if (solveRatMaze(maze, x, y - 1, sol, stack) == true)         //find path by moving left direction
                return true;

            sol[x][y] = 0;         //if both are closed, there is no path
            return false;
        }
        return false;
    }

isValidPlace只是检查该地点是否在数组，其值为0（不阻塞）

sol [] []是一个表示最终路径的数组。所有值均为1路径值为0

除外

maze [] []是给定的数组

Answer 1

您可以实现一个简单的堆栈“ visitedpaths”，该堆栈存储您已经访问过的每个坐标，并告诉老鼠不要在这些路径上走。

为此，您需要初始化一个堆栈，并初始化堆栈的顶部：

public int[] visitedpaths;    
private int top = -1 ; // that allows you to free up space to store values

然后实现一个简单的push(int v)：

public void push( int v){ 
    top = top+1;
    top = v;
}

因此，每次您的鼠标移动时，它都会将图块存储在堆栈中。

然后您必须通过修改第二个“如果”来确保它不会进入访问的图块中>