查找具有条件的矩形中的最大正方形

Question

在具有给定高度和宽度的矩形中。我应该找到大多数1的正方形，并且在标准输出上打印1的数量，在同一个正方形中也不应该有更多的2s比1s的一半，即：（（（＃1s）/ 2）> = （＃2）。 广场总是至少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。（方形是5x5的大和upperleft角位于第二排，第三列）

现在我设法写了一个能够正确执行此操作的程序，但它太慢了。

所以我。我要请一个咨询如何写算法，使其解决了这个：https://justpaste.it/1cfem下1秒（正确答案15）和本：https://justpaste.it/1cfen 4秒（正确答案556）。

编辑：我忘了用方我的意思是只有正方形的周长（四边）提

我的代码工作是这样的： 迭代海槽输入的所有字段和循环槽全部可能的广场开始在这个领域（从最大的平方可能开始）。然后，我有一些条件，比如我打破迭代，当可能的广场周长小于我已经发现的迄今为止最大数目的1时，在周围等等。当我试图找到从在给定的字段中，我记得前一个正方形的正面和左侧，然后递减（如果有1或2）。

但这还不够，因为像这样的解决方案解决了第二个输入，比如1分半钟我需要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。

现在，您将拥有4个数据结构：rowSumFor1，rowSumFor2，colSumFor1，colSumFor2。例如：rowSumFor1 [i] [j]会告诉我们在第i行中列号为0和j之间的列索引。

时间复杂度：O（宽x高）

完整代码：

#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））

编辑：

替换完整代码的伪代码。结果如预期的那样由OP提出的所有3个测试。