題意:

在一個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]);		}	}}