使用C++遞歸求解迷宮，無法處理異常情況

我正在使用我在網上找到的算法解決迷宮問題。使用C++遞歸求解迷宮，無法處理異常情況

FIND-PATH(x, y) 

if (x,y outside maze) return false 
if (x,y is goal) return true 
if (x,y not open) return false 
mark x,y as part of solution path 
if (FIND-PATH(North of x,y) == true) return true 
if (FIND-PATH(East of x,y) == true) return true 
if (FIND-PATH(South of x,y) == true) return true 
if (FIND-PATH(West of x,y) == true) return true 
unmark x,y as part of solution path 
return false

該算法適用於大多數迷宮。但它不能處理異常：

###### 
#s. # 
#.## # 
#.#### 
#...f# 
######

正如圖片所示，＃是一堵牆，空的空間可用路徑，s爲起點，f是終點。而'。'虛線是運行迷宮求解程序後標記的解決方案路徑。

在這種情況下，起始點將路徑分成兩路，在運行程序後，起點右側會有一個額外的點，這個點不能被取消標記。

我想知道有誰能指出爲什麼會發生上述算法。我應該將什麼額外的檢查添加到solve（）函數中？謝謝！

來源

2014-05-25 Dorisacat

我會建議調試代碼，看看發生了什麼事情的細節和如何可以修復它。 –

我建議使用dfs，不要再訪問訪問過的節點。在開始檢查這個條件 –

嗨。感謝您的建議。如果起點不會將路徑阻塞成兩個孤立的路徑，則該代碼在其他迷宮中可以正常工作。我試圖添加一些檢查來解決這個問題，但是他們都沒有工作到目前爲止。我會繼續嘗試：） – Dorisacat

由於您正在重新訪問已訪問的節點，可能會發生此問題。

考慮你在函數開始時考慮的額外點。現在在你的西邊，你可能錯過了檢查它是否是一個起點，並且認爲起點不是外部迷宮和可用路徑。所以現在程序再次從頭開始檢查，從而給出錯誤的結果。

儘管沒有實際的代碼，但很難調試。

編輯：它確切的問題的困擾是在談論上述

你知道從哪裏開始點。如果這樣做以下

更換

if (ch =='.' || ch == '#') 
     return false;

與

if (ch =='.' || ch == '#' || ch=='s') 
     return false;

來源

2014-05-25 07:05:17

我試圖做到這一點這樣，但事實證明，該解決方案根本不打印。因爲它從第一點開始，我猜它立即返回錯誤？ – Dorisacat

但你基本上了解我所描述的問題？我的建議使用DFS。 –

對不起，也許我以前沒有明白你的意思。你能告訴我什麼是DFS？ – Dorisacat

使用C++遞歸求解迷宮，無法處理異常情況

回答

相關問題