Pagini recente » Cod sursa (job #1525735) | Cod sursa (job #2237257) | Cod sursa (job #1591926) | Cod sursa (job #73266) | Cod sursa (job #1162149)
#include <iostream>
#include <fstream>
#include <cmath>
int min[501][501];
int splitdir[501][501];
int splitsize[501][501];
int color[501][501];
int m, n;
int c;
void fill(int ii, int jj, int p) {
c++;
for (int i = ii; i >= ii - p + 1; --i) {
for (int j = jj; j >= jj - p + 1; --j) {
color[i][j] = c;
}
}
}
void fill_color(int ii, int jj, int offseti, int offsetj)
{
if (ii == 0 || jj == 0) {
return;
}
fill(ii + offseti, jj + offsetj, splitsize[ii][jj]);
if (splitdir[ii][jj] == 1) {
// Vertical.
fill_color(ii, jj - splitsize[ii][jj], offseti, offsetj);
fill_color(ii - splitsize[ii][jj],
splitsize[ii][jj],
offseti, offsetj + jj - splitsize[ii][jj]);
} else {
// Horizontal.
fill_color(ii - splitsize[ii][jj], jj, offseti, offsetj);
fill_color(splitsize[ii][jj],
jj - splitsize[ii][jj],
offseti + ii - splitsize[ii][jj], offseti);
}
}
int main()
{
std::ifstream in("piese.in");
in >> m >> n;
in.close();
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
// Init.
min[i][j] = m * n + 1;
for (int p = 1; p <= std::min(i, j); p <<= 1) {
// Choose to split vertically.
if (1 + min[i][j - p] + min[i - p][p] < min[i][j]) {
min[i][j] = 1 + min[i][j - p] + min[i - p][p];
splitdir[i][j] = 1;
splitsize[i][j] = p;
}
// Choose to split horizontally.
if (1 + min[i - p][j] + min[p][j - p] < min[i][j]) {
min[i][j] = 1 + min[i - p][j] + min[p][j - p];
splitdir[i][j] = 2;
splitsize[i][j] = p;
}
}
}
}
std::ofstream out("piese.out");
out << min[m][n] << std::endl;
fill_color(m, n, 0, 0);
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
out << (j == 1 ? "" : " ") << color[i][j];
}
out << std::endl;
}
out.close();
return 0;
}