在 3D 数组中找到最深路径的最快方法是什么? [英] What's the fastest way to find deepest path in a 3D array?

问题描述

一个多星期以来，我一直在努力为我的问题寻找解决方案，但我找不到比百万次迭代程序更好的方法，所以我认为是时候请人帮助我了.

I've been trying to find solution to my problem for more than a week and I couldn't find out anything better than a milion iterations prog, so I think it's time to ask someone to help me.

我有一个 3D 阵列.比方说，我们谈论的是地面，第一层是表面.另一层是地下的楼层.我必须找到最深路径的长度、地下孤立洞穴的数量以及最大洞穴的大小.

I've got a 3D array. Let's say, we're talking about the ground and the first layer is a surface. Another layers are floors below the ground. I have to find deepest path's length, count of isolated caves underground and the size of the biggest cave.

这是我的问题的可视化.

Here's the visualisation of my problem.

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)

请注意，即使二楼的红色单元格与绿色单元格相邻，它也不是同一个洞穴，因为它是对角放置的，这不算数.有人告诉我，最好的方法是使用递归算法分而治之"，但我真的不知道它会是什么样子.

Note, that even though red cell on the 2nd floor is placed next to green one, It's not the same cave because it's placed diagonally and that doesn't count. I've been told that the best way to do this, might be using recursive algorithm "divide and rule" however I don't really know how could it look like.

推荐答案

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

I think you should be able to do it in O(N). When you parse your input, assign each node a 'caveNumber' initialized to 0. Set it to a valid number whenever you visit a cave:

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 之后，你就可以忽略它了.

You will visit each node 7 times at worst case: once from the outer loop, and possibly once from each of its six neighbors. But you'll only work on each one once, since after that the caveNumber is set, and you ignore it.

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

You can do the depth tracking by adding a depth parameter to the recursive ProcessNode call, and only incrementing it when visiting a lower neighbor.

这篇关于在 3D 数组中找到最深路径的最快方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！