public boolean findSolution() {
boolean finish = false; //finish should become true when a solution is found or it is determined that there is no solution
boolean success = false; //success should become true when a solution is found
//The following can be used to compute each of 8 directions
//one can move from their current position (row,column).
int[][] offset ={
{1,0}, //Down
{1,-1}, //DownLeft
{0,-1}, //Left
{-1,-1}, //UpLeft
{-1,0}, //Up
{-1,1}, //UpRight
{0,1}, //Right
{1,1} //DownRight
};
//Push information onto the stack indicating the first choice
//is the position of row 0 and column 9. The last value is face, put -1 as default
Position nextPosition = new Position(0, 9, -1);
stackSoln.push(nextPosition);
while (finish == false && stackSoln.isEmpty( ) == false) {
//check the last position
int currentRow = stackSoln.peek().getRow();
int currentCol = stackSoln.peek().getColumn();
System.out.println("Trying the position of row "
+ currentRow
+ " and column "
+ currentCol);
int newRow = -1;
int newColumn=-1;
for (int k = 0; k < 8; k++)
{
newRow = currentRow + offset[k][0];
newColumn = currentCol + offset[k][1];
//get a new position and push it
nextPosition = new Position(newRow, newColumn, -1);
stackSoln.push(nextPosition);
if (newRow < 9 && newColumn < 9 && newRow > 0 &&
newColumn > 0 && (maze[newRow][newColumn] == 'x' &&
maze[newRow][newColumn] == '.' ||
maze[newRow][newColumn] == '<' || maze[newRow][newColumn] ==
'>'))
{
if (maze[newRow][newColumn] == '<') //end of the maze
{
nextPosition.setFace(k);
success = true;
finish = true;
}
else if (maze[newRow][newColumn] == '.') //able to move
{
maze[newRow][newColumn] = 'x';
nextPosition.setFace(k);
break;
}
else
{
maze[newRow][newColumn] = 'O'; //unable to move, therefore pop the position.
stackSoln.pop();
}
if (stackSoln.isEmpty() == true)
{
success = false;
finish = true;
}
}
}
} //end of while loop
return success;
}//end of findSolution method
给定这样的输入:/image/h3s1C.png
它应该返回:
Trying the position of row 0 and column 9
Trying the position of row 1 and column 8
Trying the position of row 2 and column 7
Trying the position of row 3 and column 7
Trying the position of row 4 and column 7
Trying the position of row 4 and column 6
Trying the position of row 5 and column 5
Trying the position of row 4 and column 4
Trying the position of row 5 and column 3
Trying the position of row 6 and column 3
Trying the position of row 7 and column 3
Trying the position of row 8 and column 3
Trying the position of row 9 and column 2
Trying the position of row 9 and column 1
但是,我的代码做了类似的事情:
Trying the position of row 59834 and column 59843
Trying the position of row 59835 and column 59844
Trying the position of row 59836 and column 59845...etc
出于某种原因,如果我将 for 循环中的主 if 语句更改为 ors 而不是 ands,它会获得直到最后一个的正确值,然后出现索引越界错误。我不知道为什么,因为在这种情况下不应该使用 ors...
最佳答案
问题在于您在检查行和列是否有效之前将新位置插入堆栈。
查看代码中的这些行:
//get a new position and push it
nextPosition = new Position(newRow, newColumn, -1);
stackSoln.push(nextPosition);
不要立即将 nextPosition
压入堆栈,而是等到您验证了位置。
您可能希望将位置推送到由此 if
语句保护的 block 内的堆栈上:
if (newRow <= 9 && newColumn <= 9 && newRow > 0 &&
newColumn > 0 && (maze[newRow][newColumn] == 'x' &&
maze[newRow][newColumn] == '.' ||
maze[newRow][newColumn] == '<' || maze[newRow][newColumn] ==
'>'))
但是,条件表达式存在一些问题。您应该接受 newRow
和 newColumn
的零值。此外,检查迷宫中的字符的部分是复杂且不正确的,因为您将 &&
与 ||
混合在一起,并且因为您没有考虑 >O
个您要放入迷宫的字符。
我建议您改用这个表达式:
if (newRow >= 0 && newRow < mazeSize &&
newColumn >= 0 && newColumn < mazeSize &&
maze[newRow][newColumn] != '#')
请注意,最好使用类属性 mazeSize
而不是硬编码值。这允许表达式适用于不同的迷宫大小。
您的代码中还有其他问题超出了本问题的范围。
关于java - 迷宫解算器方法应该检查 8 个方向,却检查了根本不存在的方向,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29707876/