在3D阵列中找到最深路径的最快方法是什么？

Question

我一直试图找到解决我的问题超过一个星期的时间,我找不到任何比一个百万迭代编程更好的东西,所以我认为是时候请别人帮助我了.

我有一个3D阵列.让我们说,我们谈的是地面,第一层是一个表面.另一层是地下的地板.我必须找到最深的路径长度,地下孤立洞穴的数量和最大洞穴的大小.

这是我的问题的可视化.

Input:
5 5 5 // x, y, z
xxxxx
oxxxx
xxxxx
xoxxo
ooxxx

xxxxx
xxoxx

and so...

Output:
5 // deepest path - starting from the surface
22 // size of the biggest cave
3 // number of izolated caves (red ones) (izolated - cave that doesn't reach the surface)

请注意,即使二楼的红色电池放在绿色的旁边,它也不是同一个洞穴,因为它是对角放置的,不计算在内.我被告知最好的方法,可能是使用递归算法"划分和规则",但我真的不知道它是怎么样的.

Answer 1

我认为你应该能够在 O(N) 内完成。当您解析输入时，为每个节点分配一个初始化为 0 的“caveNumber”。每当您访问洞穴时将其设置为有效数字：

CaveCount = 0, IsolatedCaveCount=0
AllSizes = new Vector.
For each node, 
   ProcessNode(size:0,depth:0);

ProcessNode(size,depth):
   If node.isCave and !node.caveNumber 
       if (size==0) ++CaveCount
       if (size==0 and depth!=0) IsolatedCaveCount++
       node.caveNumber = CaveCount
       AllSizes[CaveCount]++
       For each neighbor of node, 
            if (goingDeeper) depth++
            ProcessNode(size+1, depth).

在最坏的情况下，您将访问每个节点 7 次：一次来自外环，也可能来自其六个邻居中的每一个。但是您只会对每个操作进行一次，因为在那之后 CaveNumber 被设置，并且您会忽略它。

您可以通过向递归 ProcessNode 调用添加深度参数来进行深度跟踪，并且仅在访问较低邻居时递增它。