我正在使用递归来解决迷宫问题 . 我的矩阵看起来像这样
char maze[][] =
{
{'#','#','#','#','#','#','#','#','#','#','#'},
{'#',' ',' ',' ',' ',' ',' ',' ',' ',' ','#'},
{'#','#','#','#',' ','#','#','#','#','#','#'},
{'#',' ',' ',' ',' ','#',' ',' ',' ',' ','X'},
{'#',' ',' ',' ',' ','#',' ',' ',' ',' ','#'},
{'#',' ','#','#','#','#','#','#',' ','#','#'},
{'#',' ',' ',' ',' ',' ',' ',' ',' ',' ','#'},
{'#','#','#','#','#','#','#','#','#','#','#'},
};
这是更大矩阵的原型 . 我的求解递归方法看起来像这样
private void solve(int x, int y) {
// set everything to false
wasHere = new boolean[maze.length][maze[1].length];
correctPath = new boolean[maze.length][maze[1].length];
for (int i = 0; i < maze.length; i++){
// Sets boolean Arrays to default values
for (int j = 0; j < maze[i].length; j++){
wasHere[i][j] = false; // set everything to false
correctPath[i][j] = false;
}
}
boolean b = solveRecursion(1,1);
System.out.println(b);
}
你可以注意到我在这里返回一个布尔值,如果我找到一条路径它应该给我一个真的 . 但它一直在给我假 . 我不确定我在solveRecursion方法中所做的逻辑错误 . 这是方法
private boolean solveRecursion(int x, int y) {
if (x == endX && y == endY){
return true;
}
if (maze[x][y] == '#' || wasHere[x][y]){
return false;
}
wasHere[x][y]=true;
if (x != 0) // Checks if not on left edge
if (solveRecursion(x-1, y)) { // Recalls method one to the left
correctPath[x][y] = true; // Sets that path value to true;
maze[x][y]='S';
return true;
}
if (x != maze[0].length ) // Checks if not on right edge
if (solveRecursion(x+1, y)) { // Recalls method one to the right
correctPath[x][y] = true;
maze[x][y]='S';
return true;
}
if (y != 0) // Checks if not on top edge
if (solveRecursion(x, y-1)) { // Recalls method one up
correctPath[x][y] = true;
maze[x][y]='S';
return true;
}
if (y != maze.length) // Checks if not on bottom edge
if (solveRecursion(x, y+1)) { // Recalls method one down
correctPath[x][y] = true;
maze[x][y]='S';
return true;
}
return false;
}
endX = 3; endY = 10;
1 回答
您对网格的坐标系感到困惑 . 在您的情况下,X表示行数,而Y表示列 .
你正在检查
if (y != maze.length)
,如果是这样你移动了"one down",实际上它正在向右移动,而不是向下移动 .这种混淆使您的Y坐标受到X值的限制 .
您应该将该行更改为:
那样可以解决问题 . 就目前而言,你永远不会达到距离结尾只有1的值(3,9),因为你的if语句检查坐标(8,9)并说:
并且从不考虑边缘值 .