Pagini recente » Cod sursa (job #2787564) | Cod sursa (job #365545) | Cod sursa (job #1244879) | Cod sursa (job #745044) | Cod sursa (job #954853)
Cod sursa(job #954853)
#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;
}