查找給定條件下2D數組中路徑的最大長度

嗨，我是堆棧溢出的新手。我需要幫助來解決下面的問題在一個Java程序查找給定條件下2D數組中路徑的最大長度

我有一個2D數組，我需要找出可以從任何節點遍歷的最大長度。如果值小於當前元素，我可以從一個元素遍歷到連接元素（左/右/上/下）。我需要找到可以有可能與在2D整數數組上述條件的最大路徑下面是5 * 5陣列

7 2 3 4 5 
    36 37 38 34 6 
    33 44 46 40 7 
    24 43 42 41 8 
    35 32 47 30 9

上述陣列中

最長路徑46-44-43-42-41 -30-9-8-7-6-5-4-3-2共有14

請幫助我在此編寫Java code.Thanks提前

來源

2013-02-03 Vasu

您好奧利查爾斯沃思，我已經嘗試過遞歸程序，我已經創建了一個相同大小的重複數組，以保持被訪問節點的軌道和堆棧與座標對象。但我不能讓它成爲可能 – Vasu

表示數據爲graph，其中G=(V,E)和V={ all squares},E = { (u,v) | u is adjacent to v and u.value < v.value)

注意上面的圖是一個Directed Acyclic Graph（因爲如果（U，V）是在E，存在要u沒有從v路徑，因爲它需要v->v1->v2->...->u使得v.value > v1.value > v2.value > .... > u.value的路徑，但operator>是傳遞所以這意味着v.value > u.value，我們知道v.value < u.value - 因爲(u,v)在E，所以這是一個矛盾，並且這樣的路徑不能存在）。

減少後 - 你可以簡單地解決longest path in a DAG，這是一個更簡單的問題。

來源

2013-02-03 14:16:02 amit

嗨阿米特我沒有太多的意識到構建一個圖可以請詳細說明我在構建圖 – Vasu

@sivakumar你讀過我鏈接到的維基文章嗎？如果您不熟悉它，請閱讀關於[圖形數據結構]的文章（http://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29），嘗試實施它並讓我知道如果您有它的一個具體問題。 – amit

據我所知，在java中沒有一個圖形的標準庫實現。寫一個滿足這個問題的要求應該相當簡單。 –

查找給定條件下2D數組中路徑的最大長度

回答

相關問題