2Dマトリックスの0と1の矩形の数はどうやって見つかりますか？

Question

私はここでSOの他のリソースをオンラインで検索しました。それらのほとんどは、私が理解している2次元行列の四角形の最大面積を求める解を提供します。しかし、長方形がで表され、1sで表される2次元行列で、矩形の数を見つける方法を知りたいのは興味深いです。

更新： 矩形として分類するものに関してシナリオを明確にしないために謝罪 - 特定の境界内の細胞が1秒でを充填された場合には、矩形であると考えられます。

Answer 1

が正しい結果与えるべき非最適化バージョンである：カウントするrectabgleについて

int sum = 0; 
for (int row = 0; row < n; row++) { 
    for (int col = 0; col < m; col++) { 
     // count all rectangles with top left corner at (row,col) 
     int upperLimit = m; // this number sets the max width that rectangles with greater 
          // height can have (depends on the 1s in the rows above) 
     for (int r = row; r < n && matrix[r][col] == 1; r++) { 
      int c = col; 
      for (; c < upperLimit && matrix[r][c] == 1; c++) 
       sum++; 
      upperLimit = c; 
     } 
    } 
} 

Answer 2

いくつかの擬似コード：

for x_0 in rows: 
    for x_1 > x_0 in rows:  # symmetry-reduction: x_0 always "top" 
     for y_0 in columns: 
      for y_1 > y_0 in columns: # symmetry reduction: y_0 always "left" 
       if mat[x_0, y_0] == mat[x_0, y_1] == mat[x_1, y_0] == mat[x_1, y_1] == 1: 
        found rectangle! 

に留意してください：それは擬似コード（一部のpython-スタイルに基づいて）とブール評価はほとんどの言語ではそのようには動作しませんよ！

対称性の低下はパフォーマンスを向上させるだけでなく、カウントしているときにも重要です。視覚的に等しく四角形があり、x_0とx_1はちょうど異なる役割を果たす（左と右の点）。あなたはこれを数える方法を決めなければなりません。

編集：上記のOle V.V.のコメントの後、私は実際には非常に異なる解釈があることに気づいた。これらのほとんどは、上記の擬似コードで実現できますが、内部レベルのチェックが異なります。しかし、それがあなたの仕事かもしれません（そして、場合によってはもっと調整されたアプローチが可能です）！

ここでは四角形がちょうど4つのコーナーで1で定義されていると仮定します。

編集：長方形のあなたの新しい定義した後に、内部チェックの変更：

if all(mat[x_0:x_1, y_0:y_1]) # python/numpy inspired pseudo-code! 

だから基本的には4ボーダーポイントで定義されたすべての値を確認することがあります。それは簡単で、あなたの問題を解決します。

もちろん、はるかに効率的である可能性があります。現在の矩形（成長している）がまだ1だけで満たされているかどうかを示すバイナリフラグを追加することが賢明かもしれません。実際には、2つのバイナリフラグ、各ディメンションごとに1つが必要になります。そうでない場合は早めに停止することができます。ここで