问题遇到的现象和发生背景
用栈来解决迷宫问题
给定迷宫起点和终点,寻找一条从起点到终点的路径。
要求搜寻策略是从起点开始按照“上、下、左、右”四个方向寻找终点,到下一个点继续按照“上、下、左、右”四个方面寻找,当该结点四个方向都搜寻完,但还没到终点时,退回到上一个点,直到找到终点或者没有路径。
比如上图从(1,1)开始,向上(0,1)不通,向下到(2,1);到了(2,1)后继续按“上、下、左、右”四个方面寻找,上已经走过,向下到(3,1);到(3,1)后上已经走过,下和左不通,向右到(3,2);到(3,2)四个方面都不通,回到(3,1)四个方向都不通,再回到(2,1),(1,1);到达(1,1)后下已经走过,左不通,继续向右走,重复这个过程最后到达(3,4)。
Input
第一行两个数m和n表示迷宫的行数和列数。迷宫大小不超过100×100
第二行四个数x1,y1,x2,y2分别表示起点和终点的坐标。
接下来是m行n列的数,用来表示迷宫,1表示墙,0表示通路。
Output
从起点到终点所经过的路径的坐标。如果不存在这样的路径则输出“No Path!”。
问题相关代码,请勿粘贴截图
运行结果及报错内容
我的解答思路和尝试过的方法
我不会用递归,要求是递归。
我想要达到的结果
希望得到不同于网上查到的源代码,用于读懂代码。
只希望得到源代码和清晰的注释。(不要百度查到的代码)
必须用栈解决,深度搜索解决