如何在2D阵列中分离和计数簇（4个方向连接的组件）？ [英] How to separate and count clusters ( 4 direction connected components) in a 2D array?

问题描述

例如，我有这样的2d数组：
 
 1 2 2 2 2 1 1 1 1 2 1 1 
 2 1 1 1 2 1 2 2 1 1 2 1 
 2 2 1 2 1 1 2 2 2 2 1 1 
 1 1 1 2 1 2 1 2 2 1 1 2 
 1 1 2 1 2 1 2 1 2 2 2 2 
 1 1 2 2 2 2 1 2 1 2 1 1 
 2 1 1 2 1 1 2 2 1 1 1 2 
 
我想标记连接组件（4个方向）是这样的：
 
 1 2 2 2 2 3 3 3 3 4 5 5 
 6 7 7 7 2 3 8 8 3 3 9 5 
 6 6 7 10 3 3 8 8 8 8 5 5 
 7 7 7 10 3 11 12 8 8 5 5 8 
 7 7 13 14 13 15 16 17 8 8 8 8 
 7 7 13 13 13 13 18 19 20 8 20 20 
 21 7 7 13 22 22 19 19 20 20 20 23 
 
标记集群的方式就像洪水填充一样，如果它连接到他们的邻居通过上下左右方向，他们将在同一个集群中进行分组。我们从左上角到右下角。请帮我解决这个问题。谢谢!!!（javascript代码示例会很棒）

我尝试过：



我为行和col制作2个循环，然后对于每个元素，我检查方向以查看它们的邻居是否是相同的数字，然后对它们进行分组。但是我总是通过这种方式发生冲突，因为我最终计算了一个新的集群，但这个数字已经属于前一个集群。

解决方案

你可以有另一个2D与第一个2D数组并行的数组。它将保存指示值所在的集群的值。这将默认为零值，表示没有集群。然后保留一个簇的计数器，从一开始，当您找到一个簇时，将其分配给簇的成员。因此，对于原始数组中的每个值，您可以查看第二个数组，它将告诉给定值所在的集群。您可以添加许多优化但这就是我将如何处理此问题。

引用：

请帮我解决这个问题。谢谢!!!（javascript代码示例会很棒）

我们不做你的HomeWork。

HomeWork不会测试你的技能在乞求其他人们做你的工作，它会让你思考并帮助你的老师检查你对你所学课程的理解，以及你应用它们时遇到的问题。

你的任何失败都会帮助你的老师发现你的弱点并设定补救措施。

所以，试一试，重读你的课程并开始工作。如果您遇到特定问题，请显示您的代码并解释这个问题，我们可能会提供帮助。



作为程序员，您的工作是创建算法解决特定问题，你不能依赖别人永远为你做，所以有一段时间你必须学会​​如何。而且越快越好。

当你要求解决方案时，就像试图通过培训其他人来学习开车一样。

创建算法基本上是找到数学并做出必要的调整以适应你的实际问题。



建议：拿一张纸并用手（机械地）解决问题。这个方法是你必须翻译成程序的。



我们就具体问题提供帮助！

所以展示你的代码并解释问题。

for example, I have 2d array like this:

 1 2 2 2 2 1 1 1 1 2 1 1
 2 1 1 1 2 1 2 2 1 1 2 1
 2 2 1 2 1 1 2 2 2 2 1 1
 1 1 1 2 1 2 1 2 2 1 1 2 
 1 1 2 1 2 1 2 1 2 2 2 2
 1 1 2 2 2 2 1 2 1 2 1 1 
 2 1 1 2 1 1 2 2 1 1 1 2

And I want to label the connected components (4 directions)to be like this:

 1  2  2  2  2  3  3  3  3  4  5  5
 6  7  7  7  2  3  8  8  3  3  9  5
 6  6  7  10 3  3  8  8  8  8  5  5
 7  7  7  10 3  11 12 8  8  5  5  8 
 7  7  13 14 13 15 16 17 8  8  8  8
 7  7  13 13 13 13 18 19 20 8  20 20 
 21 7  7  13 22 22 19 19 20 20 20 23

the way to label the clusters is like the flood fill, if it connects to their neighbor by up-down-left-right direction, they will be grouping in the same cluster. we go from top left to bottom right. Please help me solve this problem. Thanks!!!(javascript code example would be great)

What I have tried:

I make 2 for loops for row and col, then for each element, I check for directions to see if their neighbors are the same number, and then grouping them. but I always have a conflict by doing that way as I end up counting a new cluster but that number already belongs to the previous cluster.

解决方案

You could have another 2D array that is in "parallel" with the first 2D array. It would hold values that indicate which cluster a value is in. That would default to zero values meaning no cluster. Then keep a counter of clusters, beginning at one, that you assign to the members of a cluster when you find one. So for each value in the original array, you could look in your second array and it will tell which cluster a given value is in. There are lots of refinements you can add to this but that's how I would approach this problem.

Quote:

Please help me solve this problem. Thanks!!!(javascript code example would be great)

We do not do your HomeWork.
HomeWork is not set to test your skills at begging other people to do your work, it is set to make you think and to help your teacher to check your understanding of the courses you have taken and also the problems you have at applying them.
Any failure of you will help your teacher spot your weaknesses and set remedial actions.
So, give it a try, reread your lessons and start working. If you are stuck on a specific problem, show your code and explain this exact problem, we might help.

As programmer, your job is to create algorithms that solve specific problems and you can't rely on someone else to eternally do it for you, so there is a time where you will have to learn how to. And the sooner, the better.
When you just ask for the solution, it is like trying to learn to drive a car by having someone else training.
Creating an algorithm is basically finding the maths and make necessary adaptation to fit your actual problem.

advice: Take a sheet of paper and solve the problem by hand (mechanically). This method is what you must translate into program.

We give help on specific problems!
So show your code and explain the problem.

这篇关于如何在2D阵列中分离和计数簇（4个方向连接的组件）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！