UVa183 Bit Maps

分類:adhoc
n*mの01画像が与えられるので指定の形式にエンコードする。もしくはエンコード結果が与えられるので画像を復元する。再帰関数を二つ書いて終わり。

#include <iostream>

using namespace std;

char bitmap[200][200];
int lnum;

void rec(int rs, int re, int cs, int ce) {
  int sum = 0;
  for (int i = rs; i < re; i++) {
    for (int j = cs; j < ce; j++) {
      sum += bitmap[i][j] - '0';
    }
  }
  if (sum == 0) {
    if (lnum++ == 50) { lnum = 1; cout << endl; }
    cout << 0;
  }
  else if (sum == (re - rs) * (ce - cs)) {
    if (lnum++ == 50) { lnum = 1; cout << endl; }
    cout << 1;
  }
  else {
    if (lnum++ == 50) { lnum = 1; cout << endl; }
    cout << 'D';
    if (re - rs == 1) {
      int cm = (cs + ce) / 2;
      if ((ce - cs) % 2) cm++;
      rec(rs, re, cs, cm);
      rec(rs, re, cm, ce);
    }
    else if (ce - cs == 1) {
      int rm = (rs + re) / 2;
      if ((re - rs) % 2) rm++;
      rec(rs, rm, cs, ce);
      rec(rm, re, cs, ce);
    }
    else {
      int cm = (cs + ce) / 2;
      if ((ce - cs) % 2) cm++;
      int rm = (rs + re) / 2;
      if ((re - rs) % 2) rm++;
      rec(rs, rm, cs, cm);
      rec(rs, rm, cm, ce);
      rec(rm, re, cs, cm);
      rec(rm, re, cm, ce);
    }
  }
}

int rrec(int rs, int re, int cs, int ce, string &s, int p) {
  if (isdigit(s[p])) {
    for (int i = rs; i < re; i++) {
      for (int j = cs; j < ce; j++) {
        bitmap[i][j] = s[p];
      }
    }
    return p + 1;
  }
  else {
    p++;
    if (re - rs == 1) {
      int cm = (cs + ce) / 2;
      if ((ce - cs) % 2) cm++;
      p = rrec(rs, re, cs, cm, s, p);
      p = rrec(rs, re, cm, ce, s, p);
      return p;
    }
    else if (ce - cs == 1) {
      int rm = (rs + re) / 2;
      if ((re - rs) % 2) rm++;
      p = rrec(rs, rm, cs, ce, s, p);
      p = rrec(rm, re, cs, ce, s, p);
      return p;
    }
    else {
      int cm = (cs + ce) / 2;
      if ((ce - cs) % 2) cm++;
      int rm = (rs + re) / 2;
      if ((re - rs) % 2) rm++;
      p = rrec(rs, rm, cs, cm, s, p);
      p = rrec(rs, rm, cm, ce, s, p);
      p = rrec(rm, re, cs, cm, s, p);
      p = rrec(rm, re, cm, ce, s, p);
      return p;
    }
  }
}

main () {
  char format;
  while (cin >> format, format != '#') {
    int row, col;
    cin >> row >> col;
    lnum = 0;
    if (format == 'B') {
      for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
          cin >> bitmap[i][j];
        }
      }
      printf("D%4d%4d\n", row, col);
      if (row > 0 && col > 0) rec(0, row, 0, col);
      cout << endl;
    }
    else if (format == 'D') {
      string line;
      getline(cin, line);
      getline(cin, line);
      printf("B%4d%4d\n", row, col);
      rrec(0, row, 0, col, line, 0);
      for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
          if (lnum++ == 50) { lnum = 1; cout << endl; }
          cout << bitmap[i][j];
        }
      }
      cout << endl;
    }
  }
}