查找二維數組

最近入店數我有這個很煩人的問題，已被竊聽我幾個小時。我有包含數字的2D陣列。這可能是這樣的：查找二維數組

數字1是「牆」，2是入口和3是我們希望達到的點。正如你所看到的，我們有兩個3的事件，而且它們並不相等。我需要找到最近的一個。記住輸入數組是隨機的，不必看起來像這樣。

我正在考慮如何解決這些問題：先找到入口。這隻能在O完成（N^2）（最壞情況）時，因爲入口可以是陣列中的任何地方，並且不必須是沿邊緣。我可以實現這個沒有任何問題。

然後，我需要從數組中的入口點進行搜索。每當我找到了3號，我需要記住，我訪問了它，並且點（從例2和3）之間的距離。比方說，我發現離入口最遠的3號。這顯然不是最接近的點（如果我們看例子）。我需要跳回到入口並再次搜索。我想過有一種實時計數器，計數的步驟，所以，如果我曾經做更多的步驟比我剛剛發現了寶藏，我只想停下來，說，之前發現的寶藏是最接近的。

我認爲有一個更好的方式來有效地實現它，但我真的無法想象如何去做。我試圖尋找Dijkstra算法，但它似乎發現從入口到陣列中的所有號碼（號碼爲針對性3號）的最短路徑。我想你可以過濾掉其中最短的一個，但是到底你會如何在Java中實現這一點？

我不是在尋找完整的代碼，而只是爲了指導我，以便我能夠理解如何實現它。

來源

2013-04-28 Christian A

假設「距離」是指在空閒空間行走。

從入口處開始，將元素留下，向上，向下和向右移動，而如果已經標記爲已訪問，則不要進入它。如果您看到牆壁或碰到邊緣，請將其標記爲已訪問並忽略它。如果您看到空白空間，請將該元素放入隊列中。
標記訪問的入口。
出列從（1）
隊列使用取出的元素作爲新的「入口」的元素，重複（1） - （3），直到你打一個3，在這種情況下，停止。這3是最接近入口
如果你不符合任何3，你會得到一切（1），這意味着沒有3從入口到達已經訪問過。

這是你訪問哪個方向（1）可能影響最終的結果，當且僅當存在多個具有3相同的Breadth First Search一個實例，並使用類似的技術來Flood fill.

此外，，最短距離。

來源

2013-04-28 15:27:23 luiges90

我知道可以有兩個距離入口處距離相等的元素。如果是這樣的話，我只需要挑一個。但感謝評論 – 2013-04-28 15:48:39

我喜歡像這樣的問題更夫福特。當然它的N^3（在這種情況下），但它的實現起來非常簡單。

http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

你的情況：

設置創建一個二維數組ShortestDistance與無限填充。查看數組並將ShortestDistance設置爲0，如果有門。這些是我們可以在0距離內到達的網格點。

算法

 
    For itr in 0 to N // (Max Distance between any door and 
     For i in 0 to N // row index 
     For j in 0 to N //column number 
      If Grid[i][j] == 1 
       Continue; //its a wall and it can't propagate shortest distance 
      else 
       ShortestDistance[i][j] = min(
              ShortestDistance[i][j], //current value 
              1 + (ShortestDistance among all neighbours*) //reduced shortest path.

*在每個步驟中，我們正在更新到達通過到達它的鄰居+ 1中的一個，或電流值本身的最短距離的地方的最短距離。

後處理 瀏覽ShortestDistance 2D數組並打印對應於'3'類型點的最小值。

來源

2013-04-29 02:21:17 sumeet

查找二維數組

回答

相關問題