1095.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1095 on 2006-01-04 at 18:18:37 */ 
#include <cstdio>
#include <cstring>

const int MAX = 32;
const int WIDTH = 2;

class UFSet {
public:
	int parent[MAX*MAX];
	void make();
	int find(int);
	void unionSet(int, int);
};
void UFSet::make() {
	memset(parent, -1, sizeof(parent));
}
int UFSet::find(int x) {
	if(parent[x] == -1) return x;
	else {
		parent[x] = find(parent[x]);
		return parent[x];
	}
}
void UFSet::unionSet(int x, int y) {
	int pX = find(x), pY = find(y);
	if(pX != pY) parent[pX] = pY;
}

UFSet ufs;
int n, m, cross[MAX][MAX];
bool erase[MAX*MAX];
int order;

inline bool numed(int, int);
void printB(int);
void printC(int, int);

int main()
{
	int i, j;

	while(scanf("%d %d", &n, &m) != EOF && n*m != 0) {
		memset(erase, false, sizeof(erase));
		ufs.make();
		for(i = 0; i < n; i++) {
			for(j = 0; j < m; j++) {
				scanf("%d", &cross[i][j]);
				if(cross[i][j] == 1) {
					if(i != 0 && cross[i-1][j] == 1) ufs.unionSet(i*MAX+j, (i-1)*MAX+j);
					if(j != 0 && cross[i][j-1] == 1) ufs.unionSet(i*MAX+j, i*MAX+j-1);
				}
			}
		}
		for(i = 0; i < n; i++) {
			if(cross[i][0] == 1) erase[ufs.find(i*MAX)] = true;
			if(cross[i][m-1] == 1) erase[ufs.find(i*MAX+m-1)] = true;
		}
		for(i = 0; i < m; i++) {
			if(cross[0][i] == 1) erase[ufs.find(i)] = true;
			if(cross[n-1][i] == 1) erase[ufs.find((n-1)*MAX+i)] = true;
		}
		order = 0;
		printB(0);
		for(i = 0; i < n; i++) {
			for(j = 0; j < WIDTH; j++) printC(i, j);
			printB(i+1);
		}
		printf("\n\n");
	}
	
	return 0;
}

inline bool numed(int x, int y)
{
	if((x == 0 || cross[x-1][y] == 1) && (x != n-1 && cross[x+1][y] == 0)) return true;
	if((y == 0 || cross[x][y-1] == 1) && (y != m-1 && cross[x][y+1] == 0)) return true;
	return false;
}
void printB(int o) {
	int blank = 0, i, j;
	bool begin = true;
	for(i = 0; i < m; i++) {
		if((o == 0 || erase[ufs.find((o-1)*MAX+i)]) && 
			(o == n || erase[ufs.find(o*MAX+i)])) {
				blank++;
		} else {
			for(j = 0; j < blank; j++) printf("    ");
			for(j = 0; j < blank-1; j++) putchar(' ');
			if(blank != 0 && begin) putchar(' ');
			begin = false;
			if(blank != 0 || i == 0) putchar('+');
			blank = 0; printf("+++++");
		}
	}
	putchar('\n');
}
void printC(int x, int o)
{
	int blank = 0, i, j;
	bool begin = true;
	for(i = 0; i < m; i++) {
		if(cross[x][i] == 1) {
			if(erase[ufs.find(x*MAX+i)]) {
				blank++;
			} else {
				for(j = 0; j < blank; j++) printf("    ");
				for(j = 0; j < blank-1; j++) putchar(' ');
				if(blank != 0 && begin) putchar(' ');
				begin = false;
				if(blank != 0 || i == 0) putchar('+');
				blank = 0; printf("+++++");
			}
		} else {
			for(j = 0; j < blank; j++) printf("    ");
			for(j = 0; j < blank-1; j++) putchar(' ');
			if(blank != 0 && begin) putchar(' ');
			begin = false;
			if(blank != 0 || i == 0) putchar('+');
			blank = 0;
			if(o == 0 && numed(x, i)) printf("%03d +", ++order);
			else printf("    +");
		}
	}
	putchar('\n');
}