感觉非递归回溯的路径也可以通过视频中保留上一个节点的方法实现?

来源:5-7 非递归深度优先走迷宫求解最终路径

teethdiao

2020-06-18

感觉只需要判断一下是不是死路?(就是for循环并没有发生),然后返回时把isVisted全部变回false,直到目前栈里栈顶元素的上一个Position等于返回时的Position?

            int j = 0;
            for(int i=0; i<4; i++){
                int nextX = curPath.getX() + direction[i][0];
                int nextY = curPath.getY() + direction[i][1];

                if(data.inArea(nextY, nextX)
                && !data.isVisted[nextY][nextX]
                && data.getMaze(nextY, nextX)==data.ROAD) {
                    path.push(new Position(nextY, nextX,curPath));
                    data.isVisted[nextY][nextX]=true;
                    j = j+1;
                }
            }
            if(j==0){
                Position need = path.peek().getP();
                while(curPath!=need){
                    setData(curPath.getY(), curPath.getX(),false);
                    curPath = curPath.getP();
                }
            }
        }
   

图片描述
结果上看似乎没问题

写回答

1回答

liuyubobobo

2020-06-18

目测没有问题。


继续加油!:)

1
0

7个经典应用诠释Java算法精髓

课程重应用、重实践、重思维,真正应用于实际工作开发中

1888 学习 · 112 问题

查看课程