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

シンプルで高速なアルゴリズムの1つは、すべてのエントリを反復処理し、検出されたときに各領域をゼロに設定することです。これには、O（N * M）ランタイム（各エントリが最大2回アクセスされる）と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

1つの方法は、Flood Fillアルゴリズムを使用して、次のように隣接する領域を検出することです。

初期行列に正の数しかない場合、

  • を準備しcounter、に設定します-1
  • マトリックスの各ポイントについて：
  • セルがゼロまたは負の場合はスキップします。そうでなければ
  • の負の値を持つセルから始まる塗りつぶしcounter
  • 塗りつぶしが終わったら、カウンターをデクリメントします

行列の最後に到達するcounterと、負の数は連続する番号の付いた領域の数から1を引いたものに等しくなります。つまり、必要な結果はです-(counter+1)。

于 2013-01-10T01:07:17.307 に答える
1

私はいつもグループを分離するためのUnion/Findアルゴリズムが好きでした。しかし、それは私が何年も前に書いた古い実装を開始したことです。実装するのは大したことではありませんが、FloodFillを使用する方が適切な場合があります。

于 2013-01-10T01:10:00.410 に答える