1114.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1114 on 2006-01-10 at 02:36:07 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 32;

class Frame {
public:
	int l, r, u, d;
	void make();
	void update(int, int);
	void set(int[][MAX], int) const;
};
void Frame::make() {
	l = u = MAX, r = d = 0;
}
void Frame::update(int x, int y) {
	l = min(l, y), u = min(u, x), r = max(r, y), d = max(d, x);
}
void Frame::set(int p[][MAX], int n) const {
	int i;
	for(i = l; i <= r; i++) p[u][i] |= 1 << n, p[d][i] |= 1 << n;
	for(i = u; i <= d; i++) p[i][l] |= 1 << n, p[i][r] |= 1 << n;
}

bool cover[MAX][MAX], app[MAX], visit[MAX];
int fn, in[MAX];
char order[MAX];

void sort(int);

int main()
{
	Frame frame[MAX];
	char f[MAX][MAX];
	int p[MAX][MAX], w, h;
	int i, j, k;
	
	while(scanf("%d %d", &h, &w) != EOF) {
		memset(p, 0, sizeof(p)); getchar();
		memset(app, false, sizeof(app));
		for(i = 0; i < MAX; i++) frame[i].make();
		fn = 0;
		for(i = 0; i < h; i++) {
			gets(f[i]);
			for(j = 0; j < w; j++) {
				f[i][j] -= 'A';
				if(f[i][j] != '.'-'A') 
					app[f[i][j]] = true, frame[f[i][j]].update(i, j), fn = max(fn, (int)f[i][j]);
			}
		}
		fn++;
		for(i = 0; i < fn; i++)
			if(app[i]) frame[i].set(p, i);
		memset(cover, false, sizeof(cover));
		for(i = 0; i < h; i++)
			for(j = 0; j < w; j++)
				if(f[i][j] != '.'-'A')
					for(k = 0; k < fn; k++)
						if(k != f[i][j] && (p[i][j] & (1<<k)) != 0)
							cover[k][f[i][j]] = true;
		memset(in, 0, sizeof(in));
		for(i = 0; i < fn; i++)
			for(j = 0; j < fn; j++)
				if(cover[i][j]) in[j]++;
		memset(order, 0, sizeof(order));
		memset(visit, false, sizeof(visit));
		sort(0);
	}
	
	return 0;
}

void sort(int d)
{
	int i, j;
	bool end = true;
	for(i = 0; i < fn; i++) {
		if(in[i] == 0 && app[i] && !visit[i]) {
			visit[i] = true; end = false; order[d] = 'A'+i;
			for(j = 0; j < fn; j++)
				if(cover[i][j]) in[j]--;
			sort(d+1);
			for(j = 0; j < fn; j++)
				if(cover[i][j]) in[j]++;
			visit[i] = false;
		}
	}
	if(end) printf("%s\n", order);
}