3

問題は、すべてのセルが黒または白のマトリックスが与えられた場合に、すべての境界セルが黒の最大サイズのサブマトリックスを見つけることです (内部セルは黒である必要はありません)。

現在、私はせいぜいO(N^4)解決策を考えることができます。このために、2 つの補助テーブルを作成します。1 つは各セルの各行の右に連続する黒セルの数を示し、もう 1 つは各セルのその列にある連続する黒セルの数を示します。次に、次のようにします。

for each row (i):
   for each cell (i,j):
     for each window (1..n-j):
       if auxrow[i,j+window]-auxrow[i,j] == window:   #so, all cells in this window is black
         colsleft = auxcol[i,j]
         colsright = auxcol[i,j+window]
         botttom_row = min(colsleft,colsright)
         for bot in (row..row+mincol):
            if auxrow[bot][j+window]-auxrow[bot][j] == window:
              maxlen = ... #do whatever to save this sub-matrix as answer

このソリューションを改善するにはどうすればよいですか? Topcoderで興味深い議論、特に Rem ( O(N^2*log N)) による回答と Tomek によるフォローアップの改善提案を見ましたが、どちらの解決策も理解できませんでした。誰かが私よりも優れたソリューションを提供したり、それらのアルゴリズムを説明したりできますか?

4

1 に答える 1

3

O(N^3)が可能です。

各セルに対して、上と右に連続する黒いセルを計算します (O(N^2) 時間で実行できます)。

各列 (たとえば、列 i) に対して、R_i などの正しい情報を保持する n 要素の配列を 1 つ取得します。

配列 R_i が与えられた場合、次のように n 個の他の配列 (Omega(N^3) 空間) を計算します。

1 <= d <= n であるような各 d に対して、R_i の対応する値、つまり R_i[j] < d の場合、要素 j に n+1 を持つ n 要素の新しい配列 D_id を作成します。R_i[j] >= d の場合、D_id の対応するエントリは j に等しくなります。

基本的に、ad と i が与えられ、配列 D_id を使用して、i 列のどのセルが幅 d の長方形の端点になる可能性があるかを知ることができます。

ここで、範囲最小クエリの各 D_id を前処理します。つまり、範囲 [u,v] が与えられると、O(1) 時間でサブ配列 D_id[u...v] の最小値を見つけることができます。

各列に O(N^2) 時間を費やすため、このステップは O(N^3) 時間です。

四角形を見つけるには、各行を考慮し、四角形の 1 つのエッジに使用できるポイントのすべてのペアを選択します。これらの点が、長方形の左下と右下の端点であると考えてください。

検討中の点が列 i と j にあり、長方形の幅が d であるとします。

次に、長方形の可能な最大の高さを見つけます (前に計算した上部の値を使用)。hだったと言います。

検討している行が r の場合、範囲 (r, rh] の D_id で範囲最小クエリを実行します。最小値が <= n の場合、四角形が見つかりました。

考慮する可能性のあるペアは N^3 あるため (行ごとに N^2 ポイント)、合計実行時間は O(N^3) です。

于 2012-11-03T06:36:11.277 に答える