关于Move the Box中展示回溯过程的需求问题

Question

老师您好，
在Move the Box游戏中我想实现一个展示回溯算法搜索过程的功能。具体的效果就是： 当程序进行回溯搜索的时候，把当前出栈的格子用红色边框表示出来（效果类似用鼠标点击时蓝色边框表示），这样我可以直观理解这个搜索过程了。但是因为对递归的不熟悉，我没有思路去实现这个需求。请问老师可以给一条实现思路吗？

Answer 1

liuyubobobo 2021-05-05 03:18:54

最标准的实现是：你需要把整个递归算法改成非递归算法，非递归算法的每一步记录了回溯搜索的过程，对这些中间过程进行可视化。

类似这样的问题可能对你有帮助：https://leetcode-cn.com/problems/binary-search-tree-iterator/

BST 的前序遍历是一个标准的递归算法。但是如果我想看每一步搜索到了哪里，可以采用这种迭代器的思路，使用 next 来获得递归中的每一步走到了哪里。

==========

另一种实现方式是，在递归过程中添加绘制代码。但这样一来，你需要将搜索的逻辑挪到视图层，而不仅仅是数据层。

其实我们之前的程序，无论是走迷宫，还是迷宫生成，做过这样的事情：

走迷宫程序：https://git.imooc.com/coding-138/coding-138/src/master/05-Maze-Solver/05-More-about-DFS-Maze-Solver/src/AlgoVisualizer.java

其中 go 函数就是边递归，边绘制的；

迷宫生成程序：https://git.imooc.com/coding-138/coding-138/src/master/06-Maze-Generalization/03-DFS-Maze-Generalization/src/AlgoVisualizer.java

其中 go 函数就是边递归，边绘制的；

供参考。

继续加油！：）

• 提问者 慕用5485764 #1

  非常感谢！

• 提问者 慕用5485764 #2

  已经解决了，可以模拟出整个回溯过程了，谢谢老师！

• liuyubobobo 回复 提问者 慕用5485764 #3

  赞！继续加油！：）