Cod sursa(job #349879)
#include <stdio.h>
#define DIM 502
int S[DIM][DIM],A[DIM][DIM],v[]={0,1,2,4,8,16,32,64,128,256,512};
int n,m,i,j,p,q,k;
int min(int a, int b) {
return a<b?a:b;
}
int search(int x) {
int p,u,m,sol;
p = 1;
u = 10;
while (p<=u) {
m = (u-p)/2+p;
if (x>=v[m]) {
sol = m;
p = m+1;
}
else
u = m-1;
}
return v[sol];
}
int main() {
FILE *f = fopen("piese.in","r");
FILE *g = fopen("piese.out","w");
fscanf(f,"%d%d",&n,&m);
for (i=n; i>=1; i--)
for (j=m; j>=1; j--)
S[i][j] = min(min(S[i+1][j],S[i][j+1]),S[i+1][j+1])+1;
for (i=1; i<=n; i++)
for (j=1; j<=m; j++)
if (!A[i][j]) {
k++;
for (p=i; p<=i+search(S[i][j])-1; p++)
for (q=j; q<=j+search(S[i][j])-1; q++)
A[p][q] = k;
}
fprintf(g,"%d\n",k);
for (i=1; i<=n; i++) {
for (j=1; j<=m; j++)
fprintf(g,"%d ",A[i][j]);
fprintf(g,"\n");
}
fclose(f);
fclose(g);
return 0;
}