UVa 752 - Unscrambling Images

タイトル:四叉木符号化ピクチャ、ルートノード番号0、各ノード番号:親ノード*4+i(1~4).
四叉木は、サブツリーの順序を変更することによってデータを暗号化することができる.今、標準ツリーのコードをあげます.
(標準ツリー:左上から右下に0~(n^2-1))を符号化し、それを利用して他の符号ツリーを復号する.
分析:シミュレーション問題.データをテーブルにマッピングし、対応する位置を復号すればよい.関数fixを用いて,毎回再帰処理する.
もし,fix処理ノードが葉でない場合,それぞれサブツリーを処理する.現在のノードがエンコーディングテーブルにある場合、
対応するマッピング番号処理に直接変換する.そうでなければ、現在の番号処理を利用します.

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

int maps[2000];
int imge[20][20];
int mind[17]={0};

void fix( int n, int p, int m, int L )
{
	if ( n < m ) {
		for ( int i = 1 ; i <= 4 ; ++ i ) {
			if ( maps[n] ) n = maps[n];
			fix( 4*n+i, p, m, L );
		}
	}else imge[maps[n]/L][maps[n]%L] = p;
}

int main()
{
	mind[1] = 0;
	mind[2] = 1;
	mind[4] = 5;
	mind[8] = 21;
	mind[16] = 85;
	
	int T,n,m,a,b,p,l;
	while ( cin >> T )
	for ( int t = 1 ; t <= T ; ++ t ) {
		if ( t > 1 ) printf("
");
		scanf("%d",&n);
		scanf("%d",&m);
		memset( maps, 0, sizeof(maps) );
		for ( int i = 0 ; i < m ; ++ i ) {
			scanf("%d%d",&a,&b);
			maps[a] = b;
		}
		scanf("%d",&m);
		for ( int i = 0 ; i < m ; ++ i ) {
			scanf("%d%d",&p,&l);
			fix( p, l, mind[n], n );
		}
		printf("Case %d

",t);
		for ( int i = 0 ; i < n ; ++ i ) {
			for ( int j = 0 ; j < n ; ++ j )
				printf("%4d",imge[i][j]);
			printf("
");
		}
	}
	return 0;
}