hdu 5925 counts (二维离散化+dfs)

题意:

在一个R*C的地图上,有n个障碍点,问最终有多少个联通块,R,C的范围是1到1e9

结题思路:

第一次将一个二维地图离散化.

考虑x这一维的离散化,我们将障碍物之间那块长度压缩成一个点,用vetor记录下来,每个障碍物也记录下来,y这一维相同,这样我们就得到了一个最大是400*400的点,那么我们就用普通的dfs求联通块的办法去做就行了.

代码:

#include <bits/stdc++.h>using namespace std;struct node{	int x;	int y;};int vis[506][506];vector<int> nx, ny;int dx[5]={-1,0,1,0};int dy[5]={0, 1, 0,-1};long long sum;void dfs(int x, int y){	if(x<0 || x>=(int)nx.size() || y>=(int)ny.size() || y<0)return;	sum+=(long long)nx[x]*(long long)ny[y];	int i;	vis[x][y]=1;	for(i=0; i<4; i++)	{		if(vis[x+dx[i]][y+dy[i]]==0)dfs(x+dx[i], y+dy[i]);	}	return ;}int main(){	int t;	cin>>t;	int e=1; 	while(t--)	{		int r, c;		memset(vis, 0, sizeof(vis));		scanf("%d%d", &r, &c);		int n;		scanf("%d", &n);		int i, j;		node barr[305];		int x[305], y[305];		for(i=0; i<n; i++)		{			scanf("%d%d", &barr[i].x, &barr[i].y);			x[i]=barr[i].x,y[i]=barr[i].y;	 		}		x[n]=0;		x[n+1]=r;		y[n]=0;		y[n+1]=c;		sort(x, x+n+2);		sort(y, y+n+2);		int xlen, ylen;		xlen=unique(x, x+n+2)-x;		ylen=unique(y, y+n+2)-y;		map<long long, long long>numx, numy;		for(i=1; i<xlen; i++)		{			if((x[i]-x[i-1])>1)nx.push_back(x[i]-x[i-1]-1);			nx.push_back(1);			numx[x[i]]=(int)nx.size()-1;		}		for(i=1; i<ylen; i++)		{			if((y[i]-y[i-1])>1)ny.push_back(y[i]-y[i-1]-1);			ny.push_back(1);			numy[y[i]]=(int)ny.size()-1;		}		memset(vis, 0, sizeof(vis));		for(i=0; i<n; i++)		{			vis[numx[barr[i].x]][numy[barr[i].y]]=1;			}		long long ans[100005];		int top=0;		PRintf("Case #%d:/n", e++);		for(i=0; i<(int)nx.size(); i++)		{			for(j=0; j<(int)ny.size(); j++)			{				sum=0;				if(vis[i][j]==0)				{					dfs(i,j);					if(sum)	 ans[top++]=sum;				}			}		}		printf("%d/n", top);		nx.clear();		vector<int>().swap(nx);		ny.clear();		vector<int>().swap(ny);		sort(ans, ans+top);		for(i=0; i<top; i++)		{			printf(i==top-1?"%lld/n":"%lld ", ans[i]);		}	}}