天下一プログラマーコンテスト2016 予選A : D - グラフィカルグラフ

本番なんでこれを「フィジカルグラフ」と読んだんだろう…。
http://tenka1-2016-quala.contest.atcoder.jp/tasks/tenka1_2016_qualD_a

問題

各頂点にアルファベット大文字が振られた木を成す無向グラフがある。
各頂点は５つ以上辺を持たないことは保証されている。
これらを100*100以内の矩形状に並べた文字内で図示せよ。

図では頂点を表すアルファベットと辺を表す縦線横線を用いて図示する。
各辺は途中で曲げることはできない。

解法

まず辺や頂点同士が重ならないようにすることを考えよう。
適当な頂点を根として４方向に辺を伸ばす場合、深さに応じて長さを段々半々にしていけば辺や頂点は重ならない。
あとはそうして作った頂点の配置に対し、座標圧縮してやればよい。
頂点は最大26個なので、縦横51マス分の文字があれば足りる。

int N;
vector<int> E[26];
char hoge[101][101];

int did[26];
int X[26];
int Y[26];
map<int,int> XX,YY;

void dfs(int cur,int dist,int ngmask) {
	int i;
	did[cur]=1;
	XX[X[cur]]=YY[Y[cur]]=0;
	
	FOR(i,4) if((ngmask&(1<<i))==0) {
		int dd[4]={-1,0,1,0};
		FORR(e,E[cur]) if(did[e]==0) {
			X[e] = X[cur] + dd[i]*dist;
			Y[e] = Y[cur] + dd[i^1]*dist;
			dfs(e,dist/2,(i<2)?(1<<(i+2)):(1<<(i-2)));
			break;
		}
	}
	
}

void solve() {
	int i,j,k,l,r,x,y,z; string s,t;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>s>>t;
		x=s[0]-'A';
		y=t[0]-'A';
		E[x].push_back(y);
		E[y].push_back(x);
	}
	FOR(y,100) FOR(x,100) hoge[y][x]='.';
	
	dfs(0,1<<27,0);
	x=y=0;
	FORR(r,XX) r.second=x, x+=2;
	FORR(r,YY) r.second=y, y+=2;
	
	FOR(i,N) X[i]=XX[X[i]],Y[i]=YY[Y[i]], hoge[Y[i]][X[i]]='A'+i;
	FOR(i,N) {
		FORR(r,E[i]) {
			if(Y[i]<Y[r]) for(y=Y[i]+1;y<Y[r];y++) hoge[y][X[i]]='|';
			if(X[i]<X[r]) for(x=X[i]+1;x<X[r];x++) hoge[Y[i]][x]='-';
		}
	}
	cout<<"100 100"<<endl;
	FOR(y,100) cout<<hoge[y]<<endl;
}

まとめ

段々半分にすればぶつからないなーとは思ったけど、そこから座標圧縮に至れなかった。