本文共 2439 字,大约阅读时间需要 8 分钟。
我正在尝试使用递归来解决迷宫问题 . 在下面的代码中,MazeCoord是一个程序员创建的类型,用于存储坐标类型位置 . 格式为MazeCoord(int x,int y) . 我的程序现在编译,到达方法的某些部分并忽略另一个,因此在所有情况下都说“找不到路径”,只将起始位置存储在LinkedList mazePath中 . 在search()方法中有一个注释掉的部分,这是我尝试的另一种方式,但我很确定它是错误的而不是这样做的方法 .
任何帮助表示赞赏 .
递归代码:
/ **返回迷宫中的路径 . 第一个元素是起始位置,最后一个元素是退出位置 . 如果没有路径,或者在搜索之前调用此路径,则返回空列表 .
@return迷宫路径* /
public LinkedList getPath() {
return mazePath;
}
/ **如果有迷宫,找到迷宫中的路径 . 客户端可以访问通过getPath方法找到的路径 . @return是否找到了路径 . * /
public boolean search() {
currentLoc = new MazeCoord(startLoc.getRow(), startLoc.getCol());
visitedPath = new boolean[mazeData.length][mazeData[0].length];
mazePath=new LinkedList();
if(hasWallAt(startLoc) || hasWallAt(endLoc)){
return false;
}
else{
mazePath.add(currentLoc);
return appendToSearch(currentLoc.getRow(), currentLoc.getCol());
}
/**
System.out.println("try1");
mazePath.add(new MazeCoord(startLoc.getRow(), startLoc.getCol()));
boolean searchResult = appendToSearch(numRows()-1, numCols()-1);
System.out.println("test: " + searchResult);
System.out.println("test2: row, col --> " + (numRows()-1) + " , " + (numCols()-1));
System.out.println("test3: wallValue:" + hasWallAt(new MazeCoord(numRows()-1,numCols()-1)));
if(searchResult){
System.out.println("try2");
mazePath.add(new MazeCoord(numRows()-1, numCols()-1));
}
return searchResult;
*/
}
/ ** search()方法的辅助函数将执行实际递归以获取通过迷宫的路径@param行currentLoc @param col的行currentLoc @return的列如果路径可用,则为true * /
private boolean appendToSearch(int row, int col) {
//Check if within the maze
if((row - 1 < 0) || (col - 1 < 0) || (row + 1 > numRows()) || (col + 1 > numCols())){
return false;
}
//Check if the position is the exit location
if(row == endLoc.getRow() && col == endLoc.getCol()){
mazePath.add(new MazeCoord(row, col));
return false;
}
//Check for Wall
if(hasWallAt(new MazeCoord(row, col))){
return false;
}
//Check if the position has already been visited
if(visitedPath[row][col]){
return false;
}
//If all pass --> add to visitedPath
visitedPath[row][col]=true;
//Check to the Right
if(appendToSearch(row, col + 1)){
mazePath.add(new MazeCoord(row, col + 1));
return true;
}
//Check Downwards
else if(appendToSearch(row + 1, col)){
mazePath.add(new MazeCoord(row + 1, col));
return true;
}
//Check to the Left
else if(appendToSearch(row, col - 1)){
mazePath.add(new MazeCoord(row, col - 1));
return true;
}
//Check Upwards
else if(appendToSearch(row - 1, col)){
mazePath.add(new MazeCoord(row - 1, col));
return true;
}
return false;
}
转载地址:https://blog.csdn.net/weixin_33137081/article/details/115814667 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!