Recherche du plus grand carré d'un rectangle avec une condition

Question

Dans un rectangle avec une hauteur et une largeur données. Je suis censé trouver le carré avec le plus de 1 et imprimer le nombre de 1 sur stdout, aussi dans ce même carré il ne doit pas y avoir plus de 2s que la moitié de 1s, ie: ((# de 1s)/2)> = (# de 2). Le carré est toujours au moins 2x2 gros. Donc, pour l'entrée (deux premiers chiffres sont hauteur et largeur):

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 

La réponse correcte est 9. (5x5 carré est grande et le coin supérieur gauche est en deuxième rangée, troisième colonne)

Maintenant J'ai réussi à écrire un programme qui fonctionne correctement, mais c'est trop lent.

Donc, je demande un conseil comment écrire l'algorithme de sorte qu'il résout ceci: https://justpaste.it/1cfem sous 1 seconde (réponse correcte 15) et ceci: https://justpaste.it/1cfen sous 4 secondes (réponse correcte 556).

EDIT: J'ai oublié de mentionner par carré, je veux dire que le périmètre de la place (les quatre côtés)

Mon code fonctionne comme ceci: Itérer creux tous les champs de l'entrée et itérer cuvette toutes les carrés possibles qui commencent dans ce domaine (à partir du plus grand carré possible). Alors j'ai quelques conditions comme ça que je casse l'itération quand le périmètre possible du carré est plus petit que le nombre déjà le plus grand de 1 que j'ai trouvé jusqu'ici dans une perimète etc. Aussi quand j'essaye de trouver les carrés partant du champ donné, je me souviens du côté supérieur et du côté gauche du carré précédent, puis je le décrémente (s'il y en a 1 ou 2).

Mais cela ne suffit pas, car une solution comme celle-ci résout la seconde entrée en 1 minute et demi a j'en ai besoin en quatre secondes. Le code: REMARQUE: les minéraux représentent 1 et les produits toxiques représentent 2 s

#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

étape preprocess:

première matrice pré-traitement, en utilisant la méthode de somme préfixe toutes les lignes et les colonnes de sorte que vous serez capable de calculer # de 1 et # de 2 dans le périmètre du carré dans O (1).

Vous avez maintenant 4 structures de données: rowSumFor1, rowSumFor2, colSumFor1, colSumFor2. Par exemple: rowSumFor1 [i] [j] nous indiquerait le nombre de 1 dans la ligne ith pour les indices de colonne compris entre 0 et j inclus.

complexité Temps: O (lxh)

Code complet:

#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; 
} 

complexité Temps: O (wxhx min (w, h))

EDIT:

Pseudo-code remplacé avec code complet. Il en résulte comme prévu pour les 3 tests présentés par OP.