3

したがって、質問自体は非常に単純です。各入力には、幅と高さが与えられます。どちらも200を超えないため、2D平面を表す一連の0と1が与えられます。

このような。

4 5
0 0 1 1 1
0 1 1 1 1
1 1 1 1 1
1 1 1 1 1

目標は、12の領域で、右側の領域を見つけることです。言うまでもなく、長方形は1でのみ構成できます。

これを書いているときにフラッドフィルについて考えていましたが、配列内の1ごとに再評価する必要があります。これに最適なアルゴリズムは何ですか？

4

4 に答える 4

2

次の問題と同様です。合計が最大の部分行列を見つけます。これは、O（n ^ 3）アルゴリズムによって実行できます。私はあなたがstackoverflowでそれを見つけるか、インターネットで検索できると信じています。

この問題の場合、uは0を-INFに置き換えてから、上記のアルゴリズムを適用して最大の長方形領域を見つけることができます。

于 2013-01-25T15:19:02.260 に答える
1

私が考えることができる最良のアルゴリズムは、2Dマトリックスをトラバースし、左上の1つのコーナーから、この場合は右下の向きのコーナーまで、次のようにすることです。

見つけた1ごとに、1の最長の水平方向の文字列と垂直方向の文字列を見つけます。効率を上げるために、右側の位置は左側の位置より1つ少なくなっています（垂直方向の最大値を取得する必要があります）。0に達するたびにカウントを再開するだけです。次の行に到達したときにも同じことが当てはまります。

2つの数値の積は、その位置から始まる長方形の可能な最大面積です。別のデータ構造では、position、maxWidth、およびmaxHeightを格納し、最大の領域が上にある領域に基づいて順序付けを行います。効率を上げるためにサブ長方形を配置することは避けてください。これを行うには、maxHeightがそれ自体の値以下の右隣接1を無視します。データ構造の選択はあなたに任されています。

次に、作成したデータ構造を確認し、最大の長方形から始めます。最も近い0を見つけます。長方形を、0が入っている水平線を除外する2つのサブ長方形と、0が入っている垂直線を除外する2つのサブ長方形に分割します。0がエッジにある場合、3つのサブ長方形のみが取得されます。角にある場合は、2。長方形を削除し、新しく作成したサブ長方形を挿入して、最大の面積の順序を維持します。次に、0のない長方形が見つかるまで、データ構造の次の長方形でこのプロセスを繰り返します。それが最大のものです。

これは、考えられるすべての部分行列をチェックするよりも効率的です。

于 2013-01-25T17:37:03.413 に答える
1

線形の複雑さで答えることを指すコメントがいくつかありますが、単純なO（n ^ 2）アルゴリズムのように見えるものについて言及したいと思いました。

各セルについて、完全にその下にあり、完全にその左側にあるセルの数を計算します。これを線形時間で行うには、左下から行を操作し、その下のセルとその左のセルからの小計を確認します。

長方形は、左下の点と右上の点で定義できます。もちろん、四隅があります。以前に計算した左下と右上の合計を加算し、左上と右下の合計を引くと、長方形内のセルの数が得られます。長方形の外側のセルはまったくカウントされないか、キャンセルされます。その長方形が正確にどこにあるかは、コーナーケースで何をするか、および「完全にその下に、完全にその左側に」どのように解釈するかによって異なります。ただし、長方形を定義する2つのコーナーがある場合、4つの数値を取得し、加算と減算を行うことで、長方形内の合計を数えることができます。

2点で定義された長方形の場合、考慮すべきO（n ^ 2）個の長方形があります（nをデータのサイズと見なすため、検索する領域にはO（n）点があります）。各長方形内の合計を一定時間で計算し、合計がないものを破棄できるため、すべてのポイントがカバーされることを意味します。合計コストはO（n ^ 2）です。

于 2013-01-25T19:52:13.197 に答える
0 
 /*

Given a 2D binary array(2D array of 0's and 1's) with m rows and n columns,find area of largest sub-array(rectangle) 
consisting entirely of 1's.
*/

public int findMaxRectangleArea(int[][] A,int m,int n){
        // m=rows & n=cols according to question

        int[] single;
        int largeX = 0,largest = 0; 
        for (int i = 0; i < m; i++) {
              single = new int[n];            //one d array used to check line by line & it's size will be n
              for (int k = i; k < m; k++) {                // this is used for to run until i contains element
                        int a = 0;
                    int y = k - i + 1;  // is used for row and col of the comming array
                    int shrt = 0,ii = 0,small = 0; 
                                    int mix = 0;
                    int findX = 0; 
                   for (int j = 0; j < n; j++) {
                       single[j] = single[j] + A[k][j]; // postions element are added
                      if (single[j] == y) {           //element position equals
                            shrt = (a == 0) ? j : shrt;       //shortcut
                            a=a+1;
                        if (a > findX) {
                            findX = a;
                            mix = shrt;
                        }
                    } else {
                        a = 0;
                    }
                }
                   a = findX;
                   a = (a == y) ? a - 1 : a;
                         if (a * y > largeX * largest) {  // here i am checking the values with xy
                           largeX = a;
                           largest = y;
                           ii = i;
                           small = mix;
                           }
            }
        }// end of  loop

return largeX*largest;
    }       //end of method




/*
     Time complexity = method contains 2 inner loops so m*m & 1 outer loop n

     so the complexity is------------------->  O((m^2)*n)

     Space Complexity is-------it's directly proportional to the size of the array i.e ---------------> (m*m)+n

*/
于 2013-02-27T04:44:00.080 に答える