作者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/m.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