HDU 5925 离散化+dfs

题意：有一个10的9次方乘10的9次方的图，问有几个联通块，每个联通块里面有多少元素。

对于这么大的一个图，直接dfs一定会T。所以我们可以用离散化的方法。把原图拆成由众多矩形构成的图。这样我们可以用离散化，表示出每个矩形顶点的坐标。然后计算每个矩形的面积。给每个矩形是好的还是坏的打上标记。最后dfs一下联通的矩形。既可以得出答案。

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<map>using namespace std;const int maxx = 200 + 5;int x[3 * maxx], y[3 * maxx];//一共有200个点，对于每一个点，可以把原图分成8部分。共用3个坐标可以表示。map<pair<int, int>, int> vis;//数组开不了10的9次方。故用map。int r, c, n, cntx, cnty;struct node{	long long value;	bool is;}mp[maxx * 3][maxx * 3];//每个矩形是否可用，以及覆盖的面积。vector<long long> ans;int dx[] = { 1,-1,0,0 };int dy[] = { 0,0,1,-1 };long long dfs(int x, int y){	mp[x][y].is = 1;	long long now = mp[x][y].value;	for (int i = 0; i < 4; i++)	{		int xx = x + dx[i], yy = y + dy[i];		if (!mp[xx][yy].is&&xx >= 1 && xx <= cntx&&yy >= 1 && yy <= cnty)			now += dfs(xx, yy);	}	return now;}int main(){	int t;	scanf("%d", &t);	for (int i = 1; i <= t; i++)	{		scanf("%d%d%d", &r, &c, &n);		vis.clear(); cntx = 0, cnty = 0;		for (int i = 1; i <= n; i++)		{			int aa, bb;			scanf("%d%d", &aa, &bb);			x[++cntx] = aa, y[++cnty] = bb;			vis[make_pair(aa, bb)] = 1;			if (aa > 1) x[++cntx] = aa - 1;			if (bb > 1) y[++cnty] = bb - 1;			if (aa < r) x[++cntx] = aa + 1;			if (bb < c) y[++cnty] = bb + 1;		}//对于每一个点，他的左下方和右上方的点，可以切割原图为8部分。		x[++cntx] = r, y[++cnty] = c;//保存原图的边界。		sort(x + 1, x + cntx + 1);		sort(y + 1, y + cntx + 1);		cntx = unique(x + 1, x + cntx + 1) - x - 1;		cnty = unique(y + 1, y + cnty + 1) - y - 1;//去掉重复的点。		for(int i=1;i<=cntx;i++)			for (int j = 1; j <= cnty; j++)			{				int u, v;				if (i == 1)u = 1;				else u = x[i - 1] + 1;				if (j == 1) v = 1;				else v = y[j - 1] + 1;//对于i==1和j==1的情况要求矩形面积则要与（1,j）点或（i，1）点相求。//加1的目的是为了防止重复计算面积。				if (vis[make_pair(x[i], y[j])])					mp[i][j].is = 1;				else					mp[i][j].is = 0;				mp[i][j].value = (long long)(x[i] - u + 1)*(long long)(y[j] - v + 1);//矩形对角线两点相减求乘积得面积。			}		ans.clear();		for(int i=1;i<=cntx;i++)			for (int j = 1; j <= cnty; j++)			{				long long now = 0;				if (!mp[i][j].is)				{					now += dfs(i, j);					ans.push_back(now);				}			}		PRintf("Case #%d:/n", i);		printf("%d/n", ans.size());		sort(ans.begin(), ans.end());		for (int i = 0; i < ans.size(); i++)		{			if (i == 0)				printf("%lld", ans[i]);			else				printf(" %lld", ans[i]);		}		printf("/n");	}	return 0;}本人愚见，不喜勿喷。