1563.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1563 on 2006-02-15 at 16:39:58 */ 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX = 512;
const char HEX_NUM[] = "0123456789ABCDEF";

bool bit[MAX*1000], image[MAX][MAX];
int bn;

class QuadTree {
public:
	int bx, by, ex, ey, v;
	bool same;
	QuadTree *part[4];
	QuadTree(int, int, int, int);
	~QuadTree();
	void code();
	inline void set() {
		bit[bn++] = !same;
		if(same) bit[bn++] = (v == 1);
	}
};
QuadTree::QuadTree(int x1, int y1, int x2, int y2) : bx(x1), by(y1), ex(x2), ey(y2) {
	if(x1 != x2 || y1 != y2) {
		same = false;
		int mx = (x1 + x2) / 2, my = (y1 + y2) / 2;
		part[0] = new QuadTree(x1, y1, mx, my); part[1] = new QuadTree(x1, my+1, mx, y2);
		part[2] = new QuadTree(mx+1, y1, x2, my); part[3] = new QuadTree(mx+1, my+1, x2, y2);
		bool merge = true; int i;
		for(i = 0; i < 4; i++)
			if(!part[i]->same || part[i]->v != part[0]->v) merge = false;
		if(merge) {
			same = true; v = part[0]->v;
			for(i = 0; i < 4; i++) delete part[i];
		}
	} else { same = true; v = (image[x1][y1] ? 1 : 0); }
}
QuadTree::~QuadTree() {
	if(!same) {
		int i;
		for(i = 0; i < 4; i++) delete part[i];
	}
}
void QuadTree::code() {
	queue<QuadTree*> Q;
	Q.push(this); set();
	while(!Q.empty()) {
		QuadTree* p = Q.front(); Q.pop();
		if(p->same) continue;
		int i;
		for(i = 0; i < 4; i++) p->part[i]->set(), Q.push(p->part[i]);
	}
}

void print(int, int);

int main()
{
	int n, i, j, t, T;
	QuadTree *tree;
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d", &n); bn = 0;
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++) {
				int e; scanf("%d", &e);
				image[i][j] = (e == 1);
			}
		tree = new QuadTree(0, 0, n-1, n-1);
		tree->code();
		print(0, bn&3);
		for(i = bn&3; i != bn; i += 4) print(i, i+4);
		printf("\n");
		delete tree;
	}
	
	return 0;
}

void print(int b, int e)
{
	int i, v = 0;
	for(i = b; i < e; i++)
		v = (v << 1) + (bit[i] ? 1 : 0);
	putchar(HEX_NUM[v]);
}