ACM-ICPC 2010年 国内予選 問題A 角角画伯，かく悩みき

問題A:角角画伯，かく悩みき

実際に正方形を並べる必要は無し。i番目の正方形の座標を保持しつつ、上下左右の端を更新するだけ。幅は(右-左+1)、高さは(上-下+1)となる。

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int n;
int xs[200], ys[200];

int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };

int main()
{
    while (cin >> n, n) {
        int u, d, r, l;
        u = d = r = l = 0;
        xs[0] = ys[0] = 0;
        for (int i = 1; i < n; i++) {
            int s, t;
            cin >> s >> t;
            xs[i] = xs[s] + dx[t];
            ys[i] = ys[s] + dy[t];
            r = max(r, xs[i]);
            l = min(l, xs[i]);
            u = max(u, ys[i]);
            d = min(d, ys[i]);
        }
        printf("%d %d\n", r-l+1, u-d+1);
    }
    return 0;
}