各位大大好
某份作業需要解迷宮
我參考了網路上的遞迴算法
但是卻總是遇到stack overflow
想給各位抓藥一下
其中 0 是可以走的路徑
如果確定是正確路徑我就標記 1
起點為矩陣ret[1][0]
終點為ret[99][100]
https://imgur.com/LxVeeUY.jpg
terminal執行結果
https://imgur.com/inKi4aR.jpg
會stackoverflow我想是因為無法走到終止條件(?)
但是實在不知問題出在哪邊QAQ
第一次寫遞迴程式麻煩各位學長姐鞭小力一點嗚嗚
謝謝！
作者:
djshen (djshen)
2018-04-28 12:04:00你先把走的路徑印出來看跟你想的一不一樣然後先從小一點的試試看
你i,j都沒終止條件阿walk(ret,i,j+1) j會加到無限大
作者: s9041200 (小明阿) 2018-04-29 13:52:00
沒設邊界條件。如果設了還是爆掉，就用dp或單源最短路徑試試。
作者:
froce (froce)
2018-04-29 19:27:00最後一招就是改sys.setrecursionlimit()
作者:
Yshuan (倚絃)
2018-04-30 16:14:00你把size先改成30以內看是否有結果DFS可以用迴圈寫的 和BFS差別在容器是stack而非queue文章中的寫法 一個點會被重複拜訪阿 2x2也會overflow漏看line 7, 那麼就是改小size先確定這會動 再優化吧
因為你遞迴寫的方式會把整個MATRIX走滿 也就是100*100 在建立boundary情形下 先往j + 1走到底 j == 100時又往下 i + 1下走 總而言之八成會繞完整個matrix然後你not只用在一個條件下 估計走一走都是True應該八成原本標記的1都會又會變成0