算法来寻找以矩阵连接套的总数 [英] Algorithm to find the total number of connected sets in a matrix

问题描述

我想知道，我应该在这里适用的算法。将一个 DFS 办？

给定一个的2-D矩阵。找到该矩阵连接套的总数

连接组可以被定义为组电池（多个）上有提到1，并且具有在该集与它们共享邻居关系的至少一个其他细胞。用1在它的细胞和具有1在它周围没有邻居可以被认为是一组与在其一个小区。邻居可以被定义为所有相邻的8个可能的方向的（即N，W，E，S，NE，NW，东南，西南方向）的给定小区的小区。的细胞本身并不邻居。

例如：

  1 0 0 1

0 0 1 0

0 0 1 0

1 0 0 1
 

连接的集数为3

  0 0 1 0 0 1 0 0

1 0 0 0 0 0 0 1

0 0 1 0 0 1 0 1

0 1 0 0 0 1 0 0

1 0 0 0 0 0 0 0

0 0 1 1 0 1 1 0

1 0 1 1 0 1 1 0

0 0 0 0 0 0 0 0
 

连接设置的数量为9。

解决方案

我不认为你需要把它作为一般的图形问题，应用任何算法，如的 BFS 或 DFS 。

您需要做矩阵的三次扫描。

扫描1：

从顶部开始

1. 在给每个数字各1与1..N，在你的例子中的第一行会的步骤后看起来像

     

   1 0 0 2

  
2. 进入下一行，每1在行检查邻居到你的左边是无0   
     
   • 如果非0的作为在值向左
     
   • 如果0检查非0的邻居在previous线，并采取对价值的最左边的一个
     
   • 如果所有这些都为0，仅仅加1，到目前为止给出的最大数量
     
  
3. 在重复2，直到最后一行被处理
  

  和你的例子看起来应该如下

  1 0 0 2
0 0 2 0
0 0 2 0
3 0 0 2
 

扫描2：

从底部开始 检查每个邻居具有相同数量的最左边的邻居以及相同数目的在它下面的行中的相邻

基本上，如果你有一个这样的矩阵

  

1 0 2

     

1 0 2

     

0 1 0

要检查确保了一套具有真正相同的数

扫描3：

算矩阵中的唯一非0项的数量

i wanted to know which algorithm should i apply here. Would a DFS do?

Given a 2–d matrix. Find the total number of connected sets in that matrix.

Connected set can be defined as group of cell(s) which has 1 mentioned on it and have at least one other cell in that set with which they share the neighbor relationship. A cell with 1 in it and no surrounding neighbor having 1 in it can be considered as a set with one cell in it. Neighbors can be defined as all the cells adjacent to the given cell in 8 possible directions (i.e. N, W, E, S, NE, NW, SE, SW direction). A cell is not a neighbor of itself.

For example:

1 0 0 1

0 0 1 0

0 0 1 0

1 0 0 1

number of connected sets is 3

0 0 1 0 0 1 0 0

1 0 0 0 0 0 0 1

0 0 1 0 0 1 0 1

0 1 0 0 0 1 0 0

1 0 0 0 0 0 0 0

0 0 1 1 0 1 1 0

1 0 1 1 0 1 1 0

0 0 0 0 0 0 0 0

number of connected set is 9.

解决方案

I don't think you will need to think of it as a general graph problem and apply any algorithm such as BFS or DFS.

You will need to do three scans of the matrix.

scan 1:

start from the top

1. give every number each 1 with 1..n, in you example the first row would after that step would look like

   1 0 0 2

2. go to the next line and for every 1 in the row check if the neighbor to your left is non-0
   • if non-0 take on the value to the left
   • if 0 check for non-0 neighbors in the previous line and take on the value of the left most one
   • if all of those are 0 that simply add 1 to the maximum number given so far
3. repeat 2 until last line has been processed

and your example should look like follows

1 0 0 2
0 0 2 0
0 0 2 0
3 0 0 2

scan 2:

start from the bottom check if each neighbor has the same number as the left most neighbor as well as the same number as the neighbor in the row below it

basically if you have a matrix like this

1 0 2

1 0 2

0 1 0

to check ensure that a set has really the same number

scan 3:

count the number of unique non-0 entries in the matrix

这篇关于算法来寻找以矩阵连接套的总数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！