POJ 2494 - Acid Text

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

概要

\(N\) 個の画像データと \(M\) 個のルールからなる CSS 風のレイアウトの記述が与えられるので、それに従ってレンダリングしたものを答える。

制約

• \(1 \le N \le 100\)
• 各画像の幅と高さ \(w, h\) は \(1 \le w, h \le 100\)
• \(1 \le M \le 500\)
• レンダリングの結果は \(1000 \times 1000\) の領域に収まる
• CSS のルールに現れる座標は絶対値が \(10 ^ 6\) 以下の整数
• CSS のルールに現れる layer は \(10 ^ 6\) 以下の非負整数

解法

layer と出現順序による優先順位や透明なピクセルの扱いに注意しながらがんばって実装する。 入力は適度にスペースが入っているので std::istringstream で分解できる。

  1 #include <iostream>
  2 #include <sstream>
  3 #include <vector>
  4 #include <map>
  5 #include <algorithm>
  6 using namespace std;
  7 
  8 struct picture
  9 {
 10   int height, width;
 11   vector<string> bitmap;
 12 };
 13 
 14 struct object
 15 {
 16   const picture *pic;
 17   int posx, posy;
 18   string relative_to;
 19   int layer;
 20   int index;
 21 
 22   bool operator<(const object& o) const
 23   {
 24     if (layer != o.layer) {
 25       return layer < o.layer;
 26     } else {
 27       return index < o.index;
 28     }
 29   }
 30 };
 31 
 32 struct renderer
 33 {
 34   map<string, picture> pictures;
 35   map<string, object> objects;
 36 
 37   void add_object(const string& id, const string& fname, object& o)
 38   {
 39     o.pic = &pictures[fname];
 40     objects.insert(make_pair(id, o));
 41   }
 42 
 43   void render()
 44   {
 45     vector<object> v;
 46     for (map<string, object>::iterator it = objects.begin(); it != objects.end(); ++it) {
 47       fix_position(it->second);
 48       v.push_back(it->second);
 49     }
 50     int W = 0, H = 0;
 51     for (vector<object>::const_iterator it = v.begin(); it != v.end(); ++it) {
 52       W = max(W, it->posx + it->pic->width);
 53       H = max(H, it->posy + it->pic->height);
 54     }
 55     sort(v.begin(), v.end());
 56     vector<string> img(H, string(W, ' '));
 57     for (vector<object>::const_iterator it = v.begin(); it != v.end(); ++it) {
 58       for (int i = 0; i < it->pic->height; i++) {
 59         for (int j = 0; j < it->pic->width; j++) {
 60           const char src = it->pic->bitmap[i][j];
 61           if (src != ' ') {
 62             img[it->posy + i][it->posx + j] = src;
 63           }
 64         }
 65       }
 66     }
 67     for (int i = 0; i < H; i++) {
 68       cout << img[i] << endl;
 69     }
 70   }
 71 
 72   void fix_position(object& o)
 73   {
 74     if (o.relative_to.empty()) {
 75       return;
 76     }
 77     object& target = objects[o.relative_to];
 78     fix_position(target);
 79     o.posx += target.posx;
 80     o.posy += target.posy;
 81     o.relative_to = "";
 82   }
 83 };
 84 
 85 int main()
 86 {
 87   ios::sync_with_stdio(false);
 88   int T;
 89   cin >> T;
 90   for (int Ti = 1; Ti <= T; Ti++) {
 91     int N;
 92     cin >> N;
 93     renderer r;
 94     for (int i = 0; i < N; i++) {
 95       string fname;
 96       picture pic;
 97       cin >> fname >> pic.height >> pic.width;
 98       pic.bitmap.resize(pic.height);
 99       for (int j = 0; j < pic.height; j++) {
100         string& row = pic.bitmap[j];
101         cin >> row;
102         replace(row.begin(), row.end(), '.', ' ');
103       }
104       r.pictures.insert(make_pair(fname, pic));
105     }
106     int M;
107     cin >> M;
108     cin.ignore();
109     for (int i = 0; i < M; i++) {
110       string s;
111       getline(cin, s);
112       replace(s.begin(), s.end(), '#', ' ');
113       replace(s.begin(), s.end(), '{', ' ');
114       string id;
115       {
116         istringstream iss(s);
117         iss >> id;
118       }
119       object o;
120       o.index = i;
121       string file;
122       for (int j = 0; j < 5; j++) {
123         getline(cin, s);
124         replace(s.begin(), s.end(), ':', ' ');
125         replace(s.begin(), s.end(), ';', ' ');
126         replace(s.begin(), s.end(), '=', ' ');
127         istringstream iss(s);
128         string key;
129         iss >> key;
130         if (key == "pos-x") {
131           iss >> o.posx;
132         } else if (key == "pos-y") {
133           iss >> o.posy;
134         } else if (key == "position") {
135           string spec;
136           iss >> spec;
137           if (spec[0] == 'r') {
138             iss >> o.relative_to;
139           } else {
140             o.relative_to = "";
141           }
142         } else if (key == "file") {
143           iss >> file;
144         } else if (key == "layer") {
145           iss >> o.layer;
146         } else {
147           throw __LINE__;
148         }
149       }
150       getline(cin, s);
151       r.add_object(id, file, o);
152     }
153     cout << "Scenario #" << Ti << ":" << endl;
154     r.render();
155     cout << endl;
156   }
157   return 0;
158 }