Cod sursa(job #954853)

Utilizator RaduDoStochitoiu Radu RaduDo Data 30 mai 2013 11:19:40
Problema Cifra Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include<iostream>
#include<cstdio>
#define maxn 255
using namespace std;
int sum[maxn][maxn],v[maxn],n,i,i2,j,j2,k,ok;
char ch;
int main()
{
    freopen("sculptor.in","r",stdin);
    freopen("sculptor.out","w",stdout);
    scanf("%d%c",&n,&ch);
    // Păstrăm în sum[i][j] suma tuturor elementelor a[i1][j1] cu proprietatea
    // că 1 ≤ i1 ≤ i, şi 1 ≤ j1 ≤ j. Putem calcula sumele prin metoda
    // programării dinamice în complexitate O(N2) folosind formula:
    // sum[i][j] = a[i][j] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1].
    for(i=1; i<=n; ++i)
    {
        for(j=1; j<=n; ++j)
        {
            scanf("%c",&ch);
            sum[i][j] = int(ch)-48 + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];
        }
        scanf("%c",&ch);
    }
    // Acum, pentru a calcula suma elementelor din matricea cu colţurile (i1, j1) şi (i2, j2),
    // unde i1 ≤ i2 şi j1 ≤ j2, este suficient să facem calculul
    // sum[i2][j2] - sum[i1-1][j2] - sum[i2][j1-1] + sum[i1-1][j1-1].
    // Folosim "ok" pentru a evita căutarea unor pătrate de dimensiuni mai mari decât k,
    // atâta timp cât nu sunt găsite pătrate de dimensiune k.
    ok=1;
    for(k=1; k<n && ok; ++k)
    {
        ok=0;
        for(i=1; i<=n-k; ++i)
            for(j=1; j<=n-k; ++j)
            {
                i2=i+k;
                j2=j+k;
                if(sum[i2][j2]-sum[i-1][j2]-sum[i2][j-1]+sum[i-1][j-1]==(k+1)*(k+1))
                {
                    ok=1;
                    ++v[k+1];
                }
            }
    }

    for(i=2; i<=k; ++i)
        if(v[i]>0)
            printf("%d %d\n",i,v[i]);
    return 0;
}