1165-Pablo Squarson's Headache

問題概要

（略）

解説

0番目の正方形の位置を(0,0)として，全ての正方形の位置を求める．幅は，最も右にある正方形と最も左にある正方形のx座標の差+1となり，高さは，最も上にある正方形と最も下にある正方形のy座標の差+1となる．計算量はO(N)となる．

実装(C++)

#include <vector>
#include <iostream>
using namespace std;

#define REP(i,x)for(int i=0;i<(int)x;i++)
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;
vector<P> vec;
int main(){
	int xmin,ymin,xmax,ymax;
	int N;
	for(;cin>>N,N;){
		xmin=ymin=xmax=ymax=0;
		vec=vector<P>(N);
		vec[0]=P(0,0);
		REP(i,N-1){
			int n,d;
			cin>>n>>d;
			vec[i+1]=P(vec[n].first+dx[d],vec[n].second+dy[d]);
			xmax=max<int>(xmax,vec[i+1].first);
			xmin=min<int>(xmin,vec[i+1].first);
			ymax=max<int>(ymax,vec[i+1].second);
			ymin=min<int>(ymin,vec[i+1].second);
		}
		cout<<xmax+1-xmin<<" "<<ymax+1-ymin<<endl;
	}
	return 0;
}