領域を最大化する長方形を選択してください

Question

私は任意のサイズの2Dバイナリ行列を持っています。私は最大の面積を示す、この行列の矩形のセットを見つけたいと思います。制約は次のとおりです。

• 長方形は、マトリックスの "0" - フィールドと "1" - フィールドのみをカバーできます。
• 各矩形は、次の矩形から所定の距離を持たなければなりません。

ので、私はこの行列によってビットさらにこれを説明しましょう：

1 0 0 1 
0 0 0 0 
0 0 1 0 
0 0 0 0 
0 1 0 0 

は、（2つの長方形の間の最小距離は1その結果、最適解がコーナーで矩形を選択することであろうとする1 、0） - （3,1）および（1,3） - （4,3）を含む。これらの長方形は最小です。 1フィールド離れており、 "1"フィールドには存在しない。さらに、この解決法は最大面積（6 + 4 = 10）を得た。

最小距離が2の場合、エリア4 + 4 = 8の場合、最適値は（1,0） - （4,0）と（1,3） - （4,3）になります。今まで

list<rectangle> rectangles; 

struct rectangle { 
    int i,j; // bottom left corner of rectangle 
    int width,length; // width=size in neg. i direction, length=size in pos. j direction 
}; 

と：私は、リスト内のすべてのこれらの矩形を保存 Find largest rectangle containing only zeros in an N×N binary matrix

：

は今まで、私はこの記事に類似した長方形を見つけるために達成しました私はブルートフォース方式についてしか考えていませんでしたが、もちろん私はこれに満足していません。

listで対応する四角形を見つける方法のヒントとヒントを教えていただきたいと思いますが、私の問題がはっきりしていることを願っています。上記の例で

110 
000 
110 

、2最大の領域が存在する：

Answer 1

以下反例は最大面積矩形のすべての組み合わせであってもブルートフォースチェックが最適を見つけることに失敗することができることを示しています四角形、各領域3、垂直1つと水平1つ。両方を選択することはできません。したがって、これらの矩形のサブセットを選択することに制限されている場合は、合計面積3に対して1つを選択することが最善です。しかし、代わりに垂直領域3矩形また、左端の2つの0からなる最大ではない1x2の長方形を取った場合、合計5の領域が得られる可能性があります（最小離間距離は0、最小離隔距離が1の場合は独自の例では、代わりに左端の0を1x1の長方形として選択して、合計4の領域（これは3よりも優れています）でも使用できます）。

特殊距離の場合は、 ：行列内のすべての単一の0に1x1の長方形を置くことができます。離陸距離が0よりも厳密に大きい場合、私は数分前より問題がNP困難であるとは思っていませんが、まだ高速アルゴリズムは見ていません...