Q

路徑算法：如何判斷網格上從A到B到A的路徑是否繞過任何東西？

2014-07-15 52 views 0 likes

0

我需要弄清楚從A到B並返回到A的路徑是否繞過任何東西。路徑算法：如何判斷網格上從A到B到A的路徑是否繞過任何東西？

例如：這裏的路徑是APPPPPPBA。它繞過一個X，所以結果是TRUE。

XXXXXXXX 
XPPPXXXX 
XBXPXXXX 
XAPPXXXX 
XXXXXXXX

這裏的路徑是APPPPPPPBA。它不會繞過任何X，所以結果是FALSE。

XXXXXXXX 
XPPPXXXX 
XBPPXXXX 
XAPPXXXX 
XXXXXXXX

2014-07-15 ohthepain

A

回答

3

在網格周圍添加額外的X瓦片的邊框。做一個flood fill從其中一個瓦片開始標記瓷磚爲「圍繞路徑」。之後，如果所有的瓦片都是洪水填充的或部分路徑，路徑沒有包圍任何東西。（需要邊界來處理路徑將網格切割爲兩個的情況，或者，您可以在每個邊緣瓦片處開始洪水填充。）

2014-07-15 08:55:18

相關問題