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

问题描述

我一直在试图找到解决我的问题了一个多星期，我找不到任何东西比畅想反复PROG好，所以我觉得是时候请别人帮我。

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.

我有一个三维数组。比方说，我们谈论的是地面和第一层是表面。 另一层是地面以下的楼层。我必须要找到最深切的路径的长度，计算孤立的地下洞穴和最大的洞穴的大小。

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）。 当你解析你的输入，分配每个节点caveNumber初始化为0，将其设置为一个有效的数字，每当你访问一个洞穴：

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.

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