作者ar0n77777 (property)
看板Python
标题[问题]使用递回解迷宫却遇到stack overflow
时间Sat Apr 28 10:39:58 2018
各位大大好
某份作业需要解迷宫
我参考了网路上的递回算法
但是却总是遇到stack overflow
想给各位抓药一下
其中 0 是可以走的路径
如果确定是正确路径我就标记 1
起点为矩阵ret[1][0]
终点为ret[99][100]
https://imgur.com/LxVeeUY.jpg
terminal执行结果
https://imgur.com/inKi4aR.jpg
会stackoverflow我想是因为无法走到终止条件(?)
但是实在不知问题出在哪边QAQ
第一次写递回程式麻烦各位学长姐鞭小力一点呜呜
谢谢！
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.225.142.235
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Python/M.1524883201.A.A7E.html
1F：→ djshen: 你先把走的路径印出来看跟你想的一不一样 04/28 12:04
2F：→ djshen: 然後先从小一点的试试看 04/28 12:05
3F：推 a0919610611: 你i,j都没终止条件阿walk(ret,i,j+1) j会加到无限大 04/28 16:01
4F：推 s9041200: 没设边界条件。 04/29 13:52
5F：→ s9041200: 如果设了还是爆掉，就用dp或单源最短路径试试。 04/29 13:52
6F：推 froce: 最後一招就是改sys.setrecursionlimit() 04/29 19:27
感谢各位 我加入了边界条件之後还是爆掉
我加入 if i<0 or i>100 or j<0 or j>100:
return False
目前是想到还能用DFS 但也是需要用到递回
※ 编辑: ar0n77777 (140.112.25.47), 04/30/2018 14:16:31
7F：推 Yshuan: 你把size先改成30以内看是否有结果 04/30 16:14
8F：→ Yshuan: DFS可以用回圈写的 和BFS差别在容器是stack而非queue 04/30 16:15
9F：推 Yshuan: 文章中的写法 一个点会被重复拜访阿 2x2也会overflow 04/30 16:20
10F：推 Yshuan: 漏看line 7, 那麽就是改小size先确定这会动 再优化吧 04/30 16:24
11F：推 handsomeLin: 因为你递回写的方式会把整个MATRIX走满 也就是100*10 05/04 17:43
12F：→ handsomeLin: 0 在建立boundary情形下 先往j + 1走到底 j == 100 05/04 17:45
13F：→ handsomeLin: 时又往下 i + 1下走 总而言之八成会绕完整个matrix 05/04 17:46
14F：→ handsomeLin: 然後你not只用在一个条件下 估计走一走都是True 05/04 17:54
15F：→ handsomeLin: 应该八成原本标记的1都会又会变成0 05/04 17:57