0

`使用此代码时出现堆栈溢出错误。如果我们已经找到最短路径，我希望它可以工作，然后递归代码将停止。迷宫包含字符“#”和“”。如果我找到了最短路径，该路径将标有“。” 请帮忙谢谢。

public static int getCoordinateY(String location){ //to get x coordinate
    String y = location.substring(2, 4);
    int coor = (y.charAt(0) - 'Q') * 10 + Character.getNumericValue(y.charAt(1));`enter code here`
    return coor;
    }
public boolean canPass(int y,int x) { //you can keep going if you not found # and .
    if(map[y][x] == '#' || map[y][x] == '.' ) {
        return false;
    }
    return true;
}
public Character[][] cloneArray(Character[][] src) { //copy array
    int length = src.length;
    Character[][] target = new Character[length][src[0].length];
    for (int i = 0; i < length; i++) {
        System.arraycopy(src[i], 0, target[i], 0, src[i].length);
    }
    return target;
}
public void finish(int x,int y){ //goal
    xgoal=x; 
    ygoal=y;
}
public int getDistance(){ //shortest distance from shortest path
    return finalDistance;
}
public void shortestPathStart(int xStart,int yStart, int xEnd, int yEnd){
    set('S',xStart,yStart); //start coordinate
    finish(xEnd,yEnd);
    shortestPathRec(xStart+1,yStart,0,map);//to right
    shortestPathRec(xStart-1,yStart,0,map);// to left
    shortestPathRec(xStart,yStart+1,0,map);//to up
    shortestPathRec(xStart,yStart-1,0,map);// to down
    map = result; //final map with '.'
    set('F',xEnd,yEnd);
    print();
}
public void shortestPathRec(int x,int y,int step,Character[][] map){
    if(canPass(x,y)){
        step++;
        Character[][] temp = cloneArray(map);
        temp[x][y] = '.'; //in the maze, '.' using for flags
        if(x == xgoal && y == ygoal){//if already found the goal
            hasDone = true;
            finalDistance = step;
            result = temp;
            return;
        }
        if(hasDone==true && finalDistance<step){ //if shortest path is found other path should be in this condition
            return;
        }
        shortestPathRec(x+1,y,step,temp);//calltherecursive again
        shortestPathRec(x-1,y,step,temp);
        shortestPathRec(x,y+1,step,temp);
        shortestPathRec(x,y-1,step,temp);
    }
}
4

1 回答 1

0

问题分析

您未能防止物理回溯：您移动到墙上，但不是在调用堆栈中备份（撤消上一次移动），而是转到下一个递归调用并执行相反的移动 - 采取第二个无用的步骤最多备份 0 个无用步骤。您的代码将在这两个方格之间无限移动，直到超出堆栈限制。

修理

修改你的代码，这样你就永远不会走到你已经在这条路上访问过的广场。这很容易在线研究；Dijkstra 算法是最早的通用解决方案之一。

回避

学习基本调试。除此之外，在每个例程的入口和出口处插入打印语句，打印输入参数和返回值。为了更加清晰，请保留一个深度计数器并适当地缩进打印件。

于 2017-04-28T18:57:26.357 回答