1091.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1091 on 2006-02-13 at 07:52:05 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 256;
const int DIR[][2] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };

bool vst[MAX][MAX], cut[MAX][MAX][4];
int xn, yn;

int disperse(int*, int);
inline bool legal(int, int);
void DFS(int, int, bool);

int main()
{
	int x[MAX], y[MAX], n;
	int i, j;
	
	while(scanf("%d", &n) != EOF && n != 0) {
		int m = 2 * n;
		for(i = 0; i < m; i++) scanf("%d %d", &x[i], &y[i]);
		xn = disperse(x, m); yn = disperse(y, m);
		memset(cut, 0, sizeof(cut));
		for(i = 0; i < n; i++) {
			int l = min(x[2*i], x[2*i+1]), r = max(x[2*i], x[2*i+1]);
			int d = min(y[2*i], y[2*i+1]), u = max(y[2*i], y[2*i+1]);
			if(l == r) {
				for(j = d; j < u; j++) {
					if(l != 0) cut[j][l-1][1] = true;
					if(l != xn) cut[j][l][3] = true;
				}
			} else {
				for(j = l; j < r; j++) {
					if(d != 0) cut[d-1][j][2] = true;
					if(d != yn) cut[d][j][0] = true;
				}
			}
		}
		int holes = 0;
		memset(vst, false, sizeof(vst));
		for(i = 0; i < yn; i++) {
			if(!cut[i][0][3]) DFS(i, 0, true);
			if(!cut[i][xn-1][1]) DFS(i, xn-1, true);
		}
		for(i = 0; i < xn; i++) {
			if(!cut[0][i][0]) DFS(0, i, true);
			if(!cut[yn-1][i][2]) DFS(yn-1, i, true);
		}
		for(i = 0; i < yn; i++)
			for(j = 0; j < xn; j++)
				if(!vst[i][j]) { DFS(i, j, false); holes++; }
		printf("%d\n", holes);
	}
	
	return 0;
}

int disperse(int* co, int n)
{
	int dis[MAX], dn = 0, i;
	for(i = 0; i < n; i++) dis[i] = co[i];
	sort(dis, dis+n);
	for(i = 0; i < n; i++)
		if(i == 0 || dis[i] != dis[i-1]) dis[dn++] = dis[i];
	for(i = 0; i < n; i++)
		co[i] = find(dis, dis+dn, co[i]) - dis;
	return dn-1;
}
inline bool legal(int y, int x)
{
	return !(x < 0 || x >= xn || y < 0 || y >= yn);
}
void DFS(int x, int y, bool edge)
{
	int i;
	if(vst[x][y]) return;
	vst[x][y] = true;
	for(i = 0; i < 4; i++) {
		int cx = x+DIR[i][0], cy = y+DIR[i][1];
		if(legal(cx, cy) && (!edge || !cut[x][y][i])) DFS(cx, cy, edge);
	}
}