7

可能な値が 1、2、および null の n*m 行列が与えられた場合:

  . . . . . 1 . .
  . 1 . . . . . 1
  . . . 2 . . . .
  . . . . 2 . . .
  1 . . . . . 1 .
  . . . . . . . .
  . . 1 . . 2 . .
  2 . . . . . . 1

次のすべてのブロック B ((x0,y0) と (x1,y1) の間のすべての値を含む) を探しています。

  • 少なくとも 1 つの「1」を含む
  • 「2」を含まない
  • 上記のプロパティを持つ別のブロックのサブセットではありません

例：

ブロック

赤、緑、青の領域はすべて「1」を含み、「2」を含まず、より大きな領域の一部ではありません。もちろん、この写真にはそのようなブロックが 3 つ以上あります。これらすべてのブロックを見つけたいです。

これらすべての領域をすばやく見つけるにはどうすればよいでしょうか?

私は、可能なすべての長方形を繰り返し処理し、それらが最初の2つの基準を満たすかどうかを確認する、ブルートフォースソリューションを実行しています。次に、見つかったすべての長方形を反復処理し、別の長方形に含まれるすべての長方形を削除します。最初に連続する同一の行と列を削除することで、処理を高速化できます。しかし、もっと速い方法があると確信しています。

4

3 に答える 3

1

より単純な 1 次元の問題を考えてみましょう。

.2.1.1...12....2..1.1..2.1..2少なくとも 1 つを含み、そのような文字列の部分文字列では1ないすべての部分文字列を検索し2ます。これは線形時間で解決できます1。2 つの間に があるかどうかを確認するだけ2です。

これで、このアルゴリズムを 2 次元の問題に簡単に適応させることができます。

次の法則を使用して1≤i≤j≤nから までのすべての行を合計するには、、、、、および 1 次元アルゴリズムを結果の行に適用します。ij.+.=..+1=1.+2=21+1=11+2=22+2=2

複雑さ: O(n²m)。

于 2012-06-12T18:35:21.933 に答える
1

最終的に、ほぼ線形時間で機能するソリューションを見つけました (見つかった領域の数に応じて小さな要因があります)。これが最速の解決策だと思います。

この回答に触発されました: https://stackoverflow.com/a/7353193/145999 (写真もそこから撮影)

最初に、行列を列ごとに調べて、最後の '1' までのステップ数を測定する新しい行列 M1 と、最後の '2' までのステップ数を測定する行列 M2 を作成します。 M1 & M2

上の図の灰色のブロックのいずれかに「1」または「2」があると想像してください

最終的に、M1 と M2 は次のようになります。

ここに画像の説明を入力

行ごとに M1 と M2 を逆に通過しない:

ここに画像の説明を入力

次のアルゴリズムを実行します。

 foundAreas = new list()

 For each row y backwards:
     potentialAreas = new List()
     for each column x:
        if M2[x,y]>M2[x-1,y]:
            add to potentialAreas: 
                new Area(left=x,height=M2[x,y],hasOne=M1[x,y],hasTop=false)
        if M2[x,y]<M2[x-1,y]:
            for each area in potentialAreas:
                 if area.hasTop and area.hasOne<area.height:
                        add to foundAreas:
                             new Box(Area.left,y-area.height,x,y)
            if M2[x,y]==0: delete all potentialAreas
            else:
                 find the area in potentialAreas with height=M2[x,y] 
                 or the one with the closest bigger height: set its height to M2[x,y]
                 delete all potentialAreas with a bigger height

            for each area in potentialAreas:
                 if area.hasOne>M1[x,y]: area.hasOne=M1[x,y]
                 if M2[x,y+1]==0: area.hasTop=true

現在、foundAreas には、必要なプロパティを持つすべての四角形が含まれています。

于 2012-06-14T19:24:28.677 に答える
1

すべての長方形を考慮することと、適切に賢い解決策との間のどこかを見つけることができます。

たとえば、それぞれから始め1て長方形を作成し、そのエッジを外側に向かって 4 方向に徐々に拡張することができます。2 を打ったときに停止し、(a) 4 方向すべてで停止する必要があり、(b) この長方形を見たことがない場合は、この長方形を記録します。

1次に後戻りします。左上付近から赤い四角形と緑の四角形の両方を生成できるようにする必要があります。

ただし、このアルゴリズムにはかなり悪い最悪のケースがいくつかあります。すべて1の s からなる入力が頭に浮かびます。したがって、他の巧妙さ、または入力に対するいくつかの制約と組み合わせる必要があります。

于 2012-06-12T18:16:23.093 に答える