Pagini recente » Cod sursa (job #3132113) | Cod sursa (job #2141608) | Cod sursa (job #2437348) | Cod sursa (job #1257180) | Cod sursa (job #130257)
Cod sursa(job #130257)
#include <stdio.h>
const int N_MAX = 512;
int a[N_MAX][N_MAX], what[N_MAX][N_MAX];
int main()
{
freopen("piese.in", "r", stdin);
#ifndef _SCREEN_
freopen("piese.out", "w", stdout);
#endif
int N, M;
scanf("%d %d\n", &M, &N);
int i, j, cate, k;
for (i = 1; i <= M; i ++) {
for (j = 1; j <= N; j ++) {
a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + 1;
what[i][j] = 1;
for (k = 2; k <= i && k <= j; k <<= 1) {
cate = a[i - k][j] + a[i][j - k] - a[i - k][j - k] + 1;
if (cate < a[i][j]) {
a[i][j] = cate;
what[i][j] = k;
}
}
}
}
int nrp = 1, l;
for (i = M; i >= 1; i --) {
for (j = N; j >= 1; j --) {
if (what[i][j] > 0) {
for (k = i - what[i][j] + 1; k <= i; k ++) {
for (l = j - what[i][j] + 1; l <= j; l ++) {
what[k][l] = -nrp;
}
}
nrp ++;
}
}
}
printf("%d\n", a[M][N]);
for (i = 1; i <= M; i ++) {
for (j = 1; j <= N; j ++) {
printf("%d ", - what[i][j]);
}
printf("\n");
}
return 0;
}