Cod sursa(job #434940)

Utilizator points_hunterAdrian Dobrescu points_hunter Data 6 aprilie 2010 19:08:19
Problema Gutui Scor 0
Compilator c Status done
Runda teme_upb Marime 2.95 kb
#include<stdio.h>

int n;
char s[257], a[257][257], patrat[257][257], romb[257][257];
int i, j, maxp, maxr, nrp, nrr;

/*
a - matricea citita din fisier
patrat[i][j] = latura maxima a unui patrat cu coltul dreapta jos (i,j);
romb[i][j] = latura maxima a unui romb cu varful de jos la (i,j);
maxp, nrp - latura maxima si numarul patratelor cu latura maxima
maxr, nrr - latura maxima si numarul romburilor cu latura maxima
*/

int min(int a, int b, int c){
    int minim = a;
    if(b < a)
      minim = b;
    if(c < minim)
      minim = c;
    return minim;
}

int main(){
    
    freopen("figuri2.in","r",stdin);
    freopen("figuri2.out","w",stdout);
    
    //citire
    scanf("%d", &n);
    fgets(a[0], n, stdin);
    for(i = 0; i < n; i ++){
         fgets(s, n + 2, stdin);
         for(j = 0; j < n; j++)
            a[i][j] = s[j];}
         
         
    int minr;     
      
    /*   
    programare dinamica:
    
    patrat[i][j] = min{(i - 1, j), (i, j - 1), (i - 1, j - 1)} + 1, a[i][j] == 1, sau
                   0, a[i][j] == 0;
    
    calculam minimul: min romb{(i - 1, j - 1), (i - 1, j), (i - 1, j + 1)}
    romb[i][j] = min + 1, a[i][j] == 1 si exista 1 si in varful de sus
                 min, a[i][j] == 1 dar nu se poate forma romb,(0 in varful de sus)
                 0, a[i][j] ==0
    */
         
    for(i = 1; i <= n; i++)
      for(j = 1; j<= n; j++)
            if (a[i - 1][j - 1] == '1'){ // daca (i, j) este unu
              
              patrat[i][j] = min(patrat[i][j - 1], patrat[i - 1][j],
                             patrat[i - 1][j - 1]) + 1;
              
              if(patrat[i][j] > maxp){ // gasim o noua latura maxima
                maxp = patrat[i][j];
                nrp = 1; // momentan prima
              }
              else
                  if(patrat[i][j] == maxp)
                    nrp++; // alt patrat de latura maxima, pana acum
                            
              minr = min(romb[i - 1][j - 1], romb[i - 1][j], romb[i - 1][j + 1]);
              if(a[i - 2*minr - 1][j - 1] == '1')
                 romb[i][j] = minr + 1; // se poate forma romb mai mare
              else if(a[i - 2*(minr - 1) - 1][j - 1] == '1')
                  romb[i][j] = minr; // nu se poate forma romb mai mare
                  
              if(romb[i][j] > maxr){ // latura maxima de pana acum
                 maxr = romb[i][j];
                 nrr = 1; // este prima
              }
              else
                  if(romb[i][j] == maxr)
                    nrr ++; // alt romb cu latura maxima
            }
            else{ // daca (i, j) este 0. nu se poate forma cu acel colt
                  // nici romb nici patrat.
                patrat[i][j] = 0;
                romb[i][j] = 0;
            }
      
    // se afiseaza numerele cerure
    printf("%d %d\n%d %d", maxp, nrp, maxr, nrr);
    return 0;
}