Cod sursa(job #1162149)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 31 martie 2014 17:42:16
Problema Piese Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#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;
}