POJ 2873 - Apply a Cold Compress

http://poj.org/problem?id=2873

概要

あるフォーマットに従って4ビットの値の列として表現された白黒の画像データを復元して答える。

制約

解法

適当に再帰的にやるだけ。

  1 #include <iostream>
  2 #include <vector>
  3 using namespace std;
  4 
  5 typedef vector<int>::const_iterator Iterator;
  6 
  7 int gcd(int a, int b)
  8 {
  9   if (a < b) {
 10     swap(a, b);
 11   }
 12   int r;
 13   while ((r = a % b) != 0) {
 14     a = b;
 15     b = r;
 16   }
 17   return b;
 18 }
 19 
 20 int lcm(int a, int b) { return a*b/gcd(a, b); }
 21 
 22 vector<string> parse(Iterator& it)
 23 {
 24   const int tag = *it;
 25   ++it;
 26   switch (tag) {
 27     case 0:
 28       return vector<string>(1, "X");
 29     case 3:
 30       return vector<string>(1, " ");
 31     case 2:
 32       {
 33         const vector<string> left = parse(it);
 34         const vector<string> right = parse(it);
 35         const int h = lcm(left.size(), right.size());
 36         const int l = h / left.size(), r = h / right.size();
 37         vector<string> ret(h);
 38         for (int i = 0; i < h; i++) {
 39           for (int j = 0; j < l; j++) {
 40             ret[i] += left[i/l];
 41           }
 42           for (int j = 0; j < r; j++) {
 43             ret[i] += right[i/r];
 44           }
 45         }
 46         return ret;
 47       }
 48     case 1:
 49       {
 50         const vector<string> top = parse(it);
 51         const vector<string> under = parse(it);
 52         const int w = lcm(top[0].size(), under[0].size());
 53         const int t = w / top[0].size(), u = w / under[0].size();
 54         vector<string> ret;
 55         for (vector<string>::const_iterator jt = top.begin(); jt != top.end(); ++jt) {
 56           for (int j = 0; j < t; j++) {
 57             string s(w, ' ');
 58             for (int k = 0; k < w; k++) {
 59               s[k] = (*jt)[k/t];
 60             }
 61             ret.push_back(s);
 62           }
 63         }
 64         for (vector<string>::const_iterator jt = under.begin(); jt != under.end(); ++jt) {
 65           for (int j = 0; j < u; j++) {
 66             string s(w, ' ');
 67             for (int k = 0; k < w; k++) {
 68               s[k] = (*jt)[k/u];
 69             }
 70             ret.push_back(s);
 71           }
 72         }
 73         return ret;
 74       }
 75   }
 76   throw "err";
 77 }
 78 
 79 int main()
 80 {
 81   for (string line; getline(cin, line);) {
 82     vector<int> v;
 83     for (string::size_type i = 0; i < line.size(); i += 2) {
 84       v.push_back(((line[i]-'0')<<1) | (line[i+1]-'0'));
 85     }
 86     Iterator it = v.begin();
 87     const vector<string> ans = parse(it);
 88     for (string::size_type i = 0; i < ans[0].size()+2; i++) {
 89       cout << "-";
 90     }
 91     cout << endl;
 92     for (vector<string>::const_iterator jt = ans.begin(); jt != ans.end(); ++jt) {
 93       cout << "|" << *jt << "|" << endl;
 94     }
 95     for (string::size_type i = 0; i < ans[0].size()+2; i++) {
 96       cout << "-";
 97     }
 98     cout << endl;
 99   }
100   return 0;
101 }
poj/2873.cc