匹配成對搜索算法？

Question

我在http://xepthu.uhm.vn找到了一對有趣的配對遊戲。規則很簡單，你必須找到並連接兩個相同的口袋妖怪，但它們之間的路徑不被阻塞，方向不能改變3次。讓我們來看一個例子：

alt text http://img14.imageshack.us/img14/382/16170399.png

我有很多思考的算法來檢查是否有2選定的小寵物之間的路徑是有效的，但因爲我是個新手，所以我無法找到任何解決方案。你能用C＃建議我嗎？謝謝。

Answer 1

這基本上是從graph theory找到問題的路徑。網格中的字段是節點，並且所有相鄰的字段都通過邊連接。

路徑查找是一個衆所周知的問題，並且有很多算法可以解決這個問題。由於您的圖形非常小，因此這裏最好的解決方案可能只是一個蠻力算法。流行的路徑搜尋算法是Dijkstra's algorithm。

---

蠻力：開始在一些小寵物，並尋求一切可能的方式，查看是否會導致相同的寵物小精靈。如果途中被阻擋或者超過2回合，你可以停止探索。

你需要一些指針指向網格中的一個字段。指針可以向左，向右，向上或向下移動，前提是該方向上的字段未被阻止。將指針移到相鄰的字段。記住你來自哪裏以及你製作了多少回合。重複此操作直到您到達目的地。如果圈數達到3，則返回。確保您不以圓圈運行。

Answer 2

看看平面圖。您將不得不引入第二個條件：不得超過四個節點（起始節點 - 第一個方向更改 - 第二個方向更改 - 最終節點）。