在老鼠迷宫练习中,当老鼠水平移动时,我遇到了问题。我将老鼠定义为先向下(如果有的话),然后向右,然后向左。问题是,当老鼠走到一条有死胡同的路径并试图找到正确的路径时,它会混淆左右。该路径存储在一个数组中。导出位于底部的任意位置。老鼠可以向任何方向移动。 (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 simply checks if the place is in the boundaries of the array and has the value 0 (not blocking)
sol[][] is an array to represent the final path. All values are 1 except the path values that are 0
maze[][] is the given array
最佳答案
您可以实现一个简单的堆栈“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;
}
因此,每次鼠标行走时,它都会将图 block 存储在堆栈中。
那么你必须通过修改第二个“if”来确保它不会走进访问过的图 block
关于java - 迷宫回溯水平移动,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59021582/