3

我有一个这样的整数矩阵：

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

我有相同值的不同区域，由“0”分隔，我需要计算矩阵中有多少区域。我的算法基于“0”，每次发现“0”时都会出现一个新区域，所以我增加计数器。问题是我逐行搜索并多次输入同一区域。我只需要计算矩形区域。

4

4 回答 4

4

一种简单、快速的算法是遍历所有条目并在遇到每个区域时将其设置为零。这需要 O(N*M) 运行时间（每个条目最多访问两次）和 O(1) 额外内存。

要将区域设置为零，只需注意它开始的列，然后迭代到最右边的列。然后从左到右列遍历下面的行，将每个条目设置为零。

工作代码：

int count_regions( int *arr, int rows, int cols ) {
    int region_count = 0;

    for ( int first_index = 0; first_index != rows * cols; ++ first_index ) {
        if ( arr[ first_index ] == 0 ) continue;

        ++ region_count;

        int first_row = first_index / cols, first_col = first_index % cols;
        int last_col;
        for ( last_col = first_col;
              last_col != cols && arr[ first_row * cols + last_col ] != 0;
              ++ last_col ) ;

        for ( int last_row = first_row; 
              last_row != rows && arr[ last_row * cols + first_col ] != 0;
              ++ last_row ) {
            for ( int col = first_col; col != last_col; ++ col ) {
                arr[ last_row * cols + col ] = 0;
            }
        }
    }
    return region_count;
}
于 2013-01-10T01:06:59.833 回答
2

绘画技术很好。这个想法是你投下一个完全覆盖一个区域的油漆炸弹。伪代码：

for (each space) {
  if (space has been painted or is a border) continue;
  else {
    numAreas++;
    drop paint bomb
  }
}

油漆炸弹的工作原理是这样的：

paint space;
for (each adjacent space) {
  if (space has been painted or space is a border) continue;
  else {
    paint space;
    drop another bomb;
  }
}
于 2013-01-10T01:04:01.970 回答
1

一种方法是使用Flood Fill算法来检测连续区域，如下所示：

假设初始矩阵只有正数，

  • 准备一个counter，设置为-1
  • 对于矩阵中的每个点：
  • 如果单元格为零或负数，则跳过它；否则
  • 洪水填充从具有负值的单元格开始counter
  • 洪水填充结束后减少计数器

当您到达矩阵的末尾时，counter负数将等于连续编号区域的数量减一，即您需要的结果是-(counter+1)。

于 2013-01-10T01:07:17.307 回答
1

我一直很喜欢用于隔离组的 Union/Find 算法。但那是因为我有一个多年前写的旧实现。实现起来没什么大不了的，但使用 Flood Fill 可能更合适。

于 2013-01-10T01:10:00.410 回答