假設我們有下面的示例矩陣，它的元素是整數。
[[0,5,0,0,0,2],
[0,9,10,5,0,2],
[0,2,0,1,0,0],
因此，我們只想對大于零的相鄰元素求和，并使用 DFS 遞回方法回傳它們的最大和。然后，我們有sum1 = (5 9 10 5 1 2)=32，sum2 = (2 2)= 4所以，最終的答案是sum1
如何使用遞回 DFS 解決它？
uj5u.com熱心網友回復：
要對二維陣列進行深度優先搜索，您需要某種方式來跟蹤您已經訪問過哪些單元格并需要正確處理陣列的邊緣。除此之外，在使用 DFS 的情況下，最簡單的方法是為遞回函式提供一個用于運行總和的附加引數。
下面是一些 C#。我使用一組散列元組來跟蹤訪問過的單元格。另一種選擇是使用布林值的二維陣列。
class Program
{
static int MaxConnectedComponentValue( int[,] ary )
{
HashSet<(int, int)> visited = new HashSet<(int, int)>();
Func<int, int, int, int> dfs = null;
dfs = (int x, int y, int sum) => {
if (ary[x,y] == 0 || visited.Contains((x, y)))
return 0;
visited.Add((x, y));
sum = ary[x, y];
sum = (x > 0) ? dfs(x - 1, y, 0) : 0;
sum = (x < ary.GetLength(0) - 1) ? dfs(x 1, y, 0) : 0;
sum = (y > 0) ? dfs(x, y - 1, 0) : 0;
sum = (y < ary.GetLength(1) - 1) ? dfs(x, y 1, 0) : 0;
return sum;
};
int greatest = 0;
for (int y = 0; y < ary.GetLength(1); y) {
for (int x = 0; x < ary.GetLength(0); x) {
int sum = dfs(x, y, 0);
greatest = (sum > greatest) ? sum : greatest;
}
}
return greatest;
}
static void Main(string[] args)
{
int[,] ary = new int[,] {
{ 0, 5, 0, 0, 0, 2 },
{ 0, 9, 10,5, 0, 2 },
{ 0, 2, 0, 1, 0, 0 }
};
Console.WriteLine( MaxConnectedComponentValue(ary) );
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313537.html
上一篇：鏈表與二叉搜索樹插入時間復雜度