國王迷宮

Question

我正在練習參加編程比賽，我正在解決一些我以前無法回答的難題。其中之一是國王的迷宮。實質上，您會得到一個代表「令牌」的NxN數字-50<x<50。你必須從位置1,1開始（我假設在數組索引中爲0,0）並在N，N處結束。您必須在您訪問的單元格上拾取令牌，並且您無法踩入沒有令牌的單元格（由0表示）。如果你被0包圍，你就輸了。如果沒有解決方案，輸出「無解」。否則，您輸出的數字可能會從添加的令牌中累積起來。

我不知道如何解決這個問題。我想你可以寫一個迷宮算法來解決它，但這需要時間，而在編程比賽中，你只有兩個小時才能解決多個問題。我猜猜我缺少某種模式。任何人都知道我應該如何處理這個？

此外，這可能有助於提到這個問題是針對高中生。

Answer 1

這種類型的問題通常使用dynamic programming或memoization來解決。

基本上你制定了一個遞歸的解決方案，並解決它自下而上，而記住和重複使用以前計算結果。

Answer 2

認爲「圖形」算法：The Algorithm Design Manual

Answer 3

簡單的方法（即，以最簡單的代碼）是嘗試所有可能的路徑 - 嘗試每個第一步驟;對於每個第一步，嘗試每個第二步;對於每個第一步/第二步組合嘗試每個第三步;等等。然而，取決於迷宮的大小，這可能需要很長的時間才能運行（或者可能不會）。

您的下一步是想想如何更快地做到這一點。第一步通常是消除你知道不能完成的動作，或者不能達到比已有的動作更高的點。既然這是一場比賽的練習，我們會讓你自己去做這項工作。