条件がある矩形の中で最大の正方形を見つける

Question

与えられた高さと幅を持つ矩形の中に。私はほとんどの1sの正方形を見つけて、stdoutに1sの数を表示することになっています。同じ四角形でも、1sの半分よりも2s以上でなければなりません。（（of＃1s）/ 2）> = （＃of 2s）です。 正方形は常に少なくとも2x2大きくなります。今

6 8  
0 0 2 2 2 1 2 1 
0 1 2 2 1 0 1 1 
0 0 1 0 1 2 0 2 
2 1 0 2 2 1 1 1 
1 2 1 0 0 0 1 0 
1 2 0 1 1 2 1 1 

正解が9である（正方形大きな5×5であり、左上角が第二列、第3列にある）

： だから入力（最初の2つの数字は、高さと幅である）ため私はこれを正しく行うプログラムをいくらか書くことに成功しましたが、遅すぎます。

私は、この問題を解決するようにアルゴリズムを書く方法をアドバイスしています：https://justpaste.it/1cfem 1秒未満（正解15）、これはhttps://justpaste.it/1cfen（正解556）です。

編集：私は私のコードは次のように動作します私は、正方形（四辺）

の唯一の周囲を意味二乗で言及するのを忘れてしまった： 反復は、入力および反復トラフのすべてのフィールドのすべての谷可能な限り大きな正方形から始まるこのフィールドから始まる可能な正方形。それから、四角形の可能な周囲が、私が今までの周線などで見つけた1のうちの最大の数よりも小さいときに繰り返しを壊すような条件があります。また、私が四角形を見つけようとしているとき与えられたフィールドでは、前の四角形の上辺と左辺を覚えています。そしてそれを減らしてください（1または2があれば）。

しかし、これでは十分ではありません。このようなソリューションは、1秒半のような2番目の入力を4秒で解決するためです。 コード： 注：鉱物は1秒を表し、有害物質を表す2S

#include <stdio.h> 
#include <stdlib.h> 

int maxMinerals; 

void traverseforH(const int const *map, const int height, const int width) { 
    const int h1 = height - 1; 
    const int w1 = width - 1; 
    int lineOffset = 0; 
    for (int startY = 0; startY < h1; startY++) { 
     int yside = height - startY; 
     if (!(yside * 2 + (yside - 2)*2 > maxMinerals)) { 
      break; 
     } 
     for (int startX = 0; startX < w1; startX++) { 
      int xside = width - startX; 
      if (!(xside * 2 + (xside - 2)*2 > maxMinerals)) { 
       break; 
      }   
      int maxBoundl = width; 
      int maxBoundm = width; 
      if (startY + maxBoundm - height - startX > 0) { 
       maxBoundl = height; 
       maxBoundm = height; 
       if (startX - startY > 0) { 
        maxBoundl = maxBoundl + startY - startX; 
       } else { 
        maxBoundm = maxBoundm + startX - startY; 
       } 
      } else if (startY - startX > 0) { 
       maxBoundm = maxBoundm + startY - startX; 
       maxBoundl = maxBoundm; 
       maxBoundm = maxBoundm + startX - startY; 
      } else { 
       maxBoundl = maxBoundl + startY - startX; 
      } 
      int mBw = (maxBoundl - 1) * width; 

      int toxicsLeftSide = 0; 
      int mineralsLeftSide = 0; 
      int toxicsUpSide = 0; 
      int mineralsUpSide = 0; 
      int mw; 
      int lastMinerals = 0; 
      int toxics = 0; 
      int sidey = lineOffset + width; 
      for (int x = startX; x < maxBoundm; x++) { 
       mw = x + lineOffset; 
       if (map[mw] == 1) { 
        mineralsUpSide++; 
        lastMinerals++; 
       } else if (map[mw]) { 
        toxicsUpSide++; 
        toxics++; 
       } 
       mw = x + mBw; 
       if (map[mw] == 1) {   
        lastMinerals++; 
       } else if (map[mw]) { 
        toxics++; 
       } 
      } 
      for (int y = startY + 1; y < maxBoundl - 1; y++) { 
       mw = startX + sidey; 
       if (map[mw] == 1) { 
        mineralsLeftSide++; 
        lastMinerals++; 
       } else if (map[mw]) { 
        toxicsLeftSide++; 
        toxics++; 
       } 
       mw = maxBoundm - 1 + sidey; 
       if (map[mw] == 1) { 
        lastMinerals++; 
       } else if (map[mw]) { 
        toxics++; 
       } 
       sidey = sidey + width; 
      } 
      if (map[startX + mBw] == 1) { 
       mineralsLeftSide++; 
      } else if (map[startX + mBw]) { 
       toxicsLeftSide++; 
      } 

      int upsideData [2]; 
      upsideData[0] = mineralsUpSide; 
      upsideData[1] = toxicsUpSide; 

      if (!(lastMinerals/2.0 < toxics) && lastMinerals > maxMinerals) { 
       maxMinerals = lastMinerals; 
      } 
      mBw = mBw - width; 
      int noOfSquares; 
      if (xside < yside) { 
       noOfSquares = xside - 1; 
      } else { 
       noOfSquares = yside - 1; 
      } 
      for (int k = 1; k < noOfSquares; k++) { 
       int maxBoundy = maxBoundl - k; 
       int maxBoundx = maxBoundm - k; 
       if (!(((maxBoundx - startX)*2 + (maxBoundx - 2 - startX)*2) > maxMinerals)) { 
        break; 
       } 
       sidey = lineOffset + width; 
       lastMinerals = 0; 
       toxics = 0; 
       if (map[maxBoundx + lineOffset] == 1) { 
        mineralsUpSide--; 
       } else if (map[maxBoundx + lineOffset]) { 
        toxicsUpSide--; 
       } 
       if (map[startX + mBw + width] == 1) { 
        mineralsLeftSide--; 
       } else if (map[startX + mBw + width]) { 
        toxicsLeftSide--; 
       } 
       for (int x = startX + 1; x < maxBoundx; x++) { 
        mw = x + mBw; 
        if (map[mw] == 1) { 
         lastMinerals++; 
        } else if (map[mw]) { 
         toxics++; 
        } 
       } 
       for (int y = startY + 1; y < maxBoundy - 1; y++) { 
        mw = maxBoundx - 1 + sidey; 
        if (map[mw] == 1) { 
         lastMinerals++; 
        } else if (map[mw]) { 
         toxics++; 
        } 
        sidey = sidey + width; 
       } 
       int finalMinerals = lastMinerals + mineralsLeftSide + mineralsUpSide; 
       int finalToxics = toxics + toxicsLeftSide + toxicsUpSide; 
       if (!(finalMinerals/2.0 < finalToxics) && finalMinerals > maxMinerals) { 
        maxMinerals = finalMinerals; 
       } 
       mBw = mBw - width; 


      } 

     } 
     lineOffset = lineOffset + width; 
    } 
    printf("%d\n", maxMinerals); 
} 

void traverseforW(int *map, const int height, const int width) { 
    int h1 = height - 1; 
    int w1 = width - 1; 
    int lineOffset = 0; 
    for (int startY = 0; startY < h1; startY++) { 
     int yside = height - startY; 
     if (!(yside * 2 + (yside - 2)*2 > maxMinerals)) { 
      break; 
     } 
     for (int startX = 0; startX < w1; startX++) { 
      int xside = width - startX; 
      if (!(xside * 2 + (xside - 2)*2 > maxMinerals)) { 
       break; 
      } 
      int maxBoundl = height; 
      int maxBoundm = height; 
      if (startX + maxBoundl - width - startY > 0) { 
       maxBoundl = width; 
       maxBoundm = width; 
       if (startX - startY > 0) { 
        maxBoundl = maxBoundl + startY - startX; 
       } else { 
        maxBoundm = maxBoundm + startX - startY; 
       } 
      } else if (startY - startX > 0) { 
       maxBoundm = maxBoundm + startX - startY; 
      } else { 
       maxBoundl = maxBoundl + startX - startY; 
       maxBoundm = maxBoundl; 
       maxBoundl = maxBoundl + startY - startX; 
      } 
      int mBw = (maxBoundl - 1) * width; 

      int toxicsLeftSide = 0; 
      int mineralsLeftSide = 0; 
      int toxicsUpSide = 0; 
      int mineralsUpSide = 0; 
      int mw; 
      int lastMinerals = 0; 
      int toxics = 0; 
      int sidey = lineOffset + width; 
      for (int x = startX; x < maxBoundm; x++) { 
       mw = x + lineOffset; 
       if (map[mw] == 1) { 
        mineralsUpSide++; 
        lastMinerals++; 
       } else if (map[mw]) { 
        toxicsUpSide++; 
        toxics++; 
       } 
       mw = x + mBw; 
       if (map[mw] == 1) {    
        lastMinerals++; 
       } else if (map[mw]) { 
        toxics++; 
       } 
      } 
      for (int y = startY + 1; y < maxBoundl - 1; y++) { 
       mw = startX + sidey; 
       if (map[mw] == 1) { 
        mineralsLeftSide++; 
        lastMinerals++; 
       } else if (map[mw]) { 
        toxicsLeftSide++; 
        toxics++; 
       } 
       mw = maxBoundm - 1 + sidey; 
       if (map[mw] == 1) { 
        lastMinerals++; 
       } else if (map[mw]) { 
        toxics++; 
       } 
       sidey = sidey + width; 
      } 
      if (map[startX + mBw] == 1) { 
       mineralsLeftSide++; 
      } else if (map[startX + mBw]) { 
       toxicsLeftSide++; 
      } 
      if (!(lastMinerals/2.0 < toxics) && lastMinerals > maxMinerals) { 
       maxMinerals = lastMinerals; 
      } 
      mBw = mBw - width; 

      int noOfSquares; 
      if (xside < yside) { 
       noOfSquares = xside - 1; 
      } else { 
       noOfSquares = yside - 1; 
      } 
      for (int k = 1; k < noOfSquares; k++) { 
       int maxBoundy = maxBoundl - k; 
       int maxBoundx = maxBoundm - k; 
       if (!(((maxBoundx - startX)*2 + (maxBoundx - 2 - startX)*2) > maxMinerals)) {  
        break; 
       } 
       sidey = lineOffset + width; 
       lastMinerals = 0; 
       toxics = 0; 
       if (map[maxBoundx + lineOffset] == 1) { 
        mineralsUpSide--; 
       } else if (map[maxBoundx + lineOffset]) { 
        toxicsUpSide--; 
       } 
       if (map[startX + mBw + width] == 1) { 
        mineralsLeftSide--; 
       } else if (map[startX + mBw + width]) { 
        toxicsLeftSide--; 
       } 
       int finalMinerals = mineralsUpSide + mineralsLeftSide; 
       int finalToxics = toxicsLeftSide + toxicsUpSide; 
       for (int x = startX + 1; x < maxBoundx; x++) { 
        mw = x + mBw; 
        if (map[mw] == 1) { 
         lastMinerals++; 
        } else if (map[mw]) { 
         toxics++; 
        } 
       } 
       for (int y = startY + 1; y < maxBoundy - 1; y++) { 
        mw = maxBoundx - 1 + sidey; 
        if (map[mw] == 1) { 
         lastMinerals++; 
        } else if (map[mw]) { 
         toxics++; 
        } 
        sidey = sidey + width; 
       } 
       finalMinerals += lastMinerals; 
       finalToxics += toxics; 
       if (!(finalMinerals/2.0 < finalToxics) && finalMinerals > maxMinerals) { 
        maxMinerals = finalMinerals; 
       } 
       mBw = mBw - width; 
      } 
     } 
     lineOffset = lineOffset + width; 
    } 
    printf("%d\n", maxMinerals); 
} 

int main() { 
    char hw[14]; 
    FILE * file = fopen("pub01.in", "r"); 
    char c; 
    int k = 0; 
    while ((c = fgetc(file)) != '\n') { 
     hw[k] = c; 
     k++; 
    } 
    int h, w; 
    sscanf(hw, "%d %d", &h, &w); 
    int size = h * w; 
    int* input = malloc(size * sizeof (int) + 1); 
    k = 0; 
    while ((c = fgetc(file)) != EOF) { 
     if (c == '0' || c == '1' || c == '2') { 
      input[k] = c - '0'; 
      k++; 
     } 
    } 
    input[k] = '\0'; 
    if (h > w) { 
     traverseforH(input, h, w); 
    } else { 
     traverseforW(input, h, w); 
    } 
    return 0; 
} 

Answer 1

プリプロセスステップ：

まず前処理行列、あなたがなりますように、すべての行と列をプレフィックス和法を用いて、 O（1）の四角形の周りの1の数と2の数を計算することができます。

これで、rowSumFor1、rowSumFor2、colSumFor1、colSumFor2の4つのデータ構造が得られます。たとえば、rowSumFor1 [i] [j]は、0からjの間の列インデックスに対して、i行目の1の数を示します。

時間複雑：O（WxH）総

完全コード：

#include<stdio.h> 


int min(int a,int b){ 
    return (a<=b)?a:b; 
} 

int max(int a,int b){ 
    return (a>=b)?a:b; 
} 

// currently hard-coding dimensions for test purposes 
// horizontal sums 
int rowSumFor1[600][600]; 
int rowSumFor2[600][600]; 

// vertical sums 
int colSumFor1[600][600]; 
int colSumFor2[600][600]; 

int main(){ 


    int w,h; 

    scanf("%d %d",&h,&w); 



    for(int row=1;row <= h;row++)for(int col=1;col <= w;col++){ 

     int temp; 

     scanf("%d",&temp); 

     // first add previous sum 
     rowSumFor1[row][col]=rowSumFor1[row][col - 1]; 
     rowSumFor2[row][col]=rowSumFor2[row][col - 1]; 

     colSumFor1[col][row]=colSumFor1[col][row - 1]; 
     colSumFor2[col][row]=colSumFor2[col][row - 1]; 

     if(temp==1){ 
      rowSumFor1[row][col]++; 
      colSumFor1[col][row]++; 
     } 
     else if(temp==2){ 
      rowSumFor2[row][col]++; 
      colSumFor2[col][row]++; 
     } 
     else{ 
      // do nothing 
     } 
    } 

    int result = 0,rowId,colId,mlength; 

    for(int len=min(w,h); len > 1 ; len--) // iteration on possible lengths 
    { 
     for(int row=1;row <= (h - len + 1);row++)for(int col=1;col <= (w - len + 1);col++){ // iteration on all co-ordinates as upper-left corner of our square 

     // Do calculation here for properties and necessary checking constraints for validity of this square 

     // Note: not checking trivial conditions like boundary conditions in square, you will have to!! 

      // Beware of over-counting of corners here, one way to avoid is to select indices such that they don't overcount corners 

      // 4x4 square example for counting 
      // aaab 
      // d b 
      // d b 
      // dccc 

      int topEdge1 = rowSumFor1[row][col + len - 2] - rowSumFor1[row][col - 1]; 
      int bottomEdge1 = rowSumFor1[row + len - 1][col + len - 1] - rowSumFor1[row + len - 1][col]; 
      int leftEdge1 = colSumFor1[col][row + len - 1] - colSumFor1[col][row]; 
      int rightEdge1 = colSumFor1[col + len - 1][row + len - 2] - colSumFor1[col + len - 1][row - 1]; 

      int ones= topEdge1 + bottomEdge1 + leftEdge1 + rightEdge1; // # of 1s on perimeter of this square 



      int topEdge2 = rowSumFor2[row][col + len - 2] - rowSumFor2[row][col-1]; 
      int bottomEdge2 = rowSumFor2[row+len-1][col+len-1] - rowSumFor2[row+len-1][col]; 
      int leftEdge2 = colSumFor2[col][row + len - 1] - colSumFor2[col][row]; 
      int rightEdge2 = colSumFor2[col + len - 1][row + len - 2] - colSumFor2[col + len -1][row - 1]; 

      int twos= topEdge2 + bottomEdge2 + leftEdge2 + rightEdge2; // # of 2s on perimeter of this square 


      if(ones >= 2* twos){ 
       if(ones > result){ 
        result = ones; 
        rowId = row; 
        colId = col; 
        mlength = len; 
       } 
      } 
     } 

    } 

    printf("%d %d %d\n",rowId,colId,mlength); 
    printf("%d\n",result); 

    return 0; 
} 

時間複雑：O（wxhx分（W、H））

EDIT：

擬似コードを完全なコードに置き換えました。これは、OPによって提示された3つの試験すべてについて期待される結果である。