Coconuts

23 321 22 13 312 2 Sample Output
Case #1:21 6Case #2:18
一個(gè)求有多少個(gè)聯(lián)通塊的題目，數(shù)據(jù)量比較大，需要對(duì)點(diǎn)的坐標(biāo)分別離散化。
#include <iostream>#include <algorithm>#include <vector>#include <cstring>#include <string>#include <cstdio>using namespace std;const int Size = 1024;int T;//測(cè)試數(shù)據(jù)int Case = 1;int R,C;int Q;vector<long long>Area;//存儲(chǔ)每一塊聯(lián)通塊的面積int x[Size];int y[Size];int temp[Size];int lenx[Size];//x方向每一段的長(zhǎng)度；int leny[Size];//y方向每一段的長(zhǎng)度；int Pos[Size];int cntx,cnty;bool book[Size][Size];int dx[] = {1, -1, 0, 0};int dy[] = {0, 0, -1, 1};long long dfs(int x, int y){	long long sum = (long long)lenx[x]*leny[y];	book[x][y] = true;	for(int i=0; i<4; i++)	{		int _x = x+dx[i];		int _y = y+dy[i];		if(!book[_x][_y] && _x>=1 && _x<=cntx && _y>=1 && _y<=cnty)			sum += dfs(_x,_y);	}	return sum;}int main(){	cin>>T;	while(T--)	{		//Initial		Area.clear();		//Input		cin>>R>>C;		cin>>Q;		for(int i=0; i<Q; i++)			cin>>x[i]>>y[i];		//離散化x軸		int index = 0;		temp[index++] = 0;		temp[index++] = R;		for(int i=0; i<Q; i++)			temp[index++] = x[i];//將bad coconuts的x坐標(biāo)以及邊界存起來(lái)		sort(temp, temp+index);//對(duì)x坐標(biāo)排序		index = unique(temp, temp+index)-temp;//對(duì)x坐標(biāo)去重		cntx = 0;//x軸離散的段數(shù)		for(int i=1; i<index; i++)//求每一段的長(zhǎng)度		{			if(temp[i] > temp[i-1]+1)				lenx[++cntx] = temp[i]-(temp[i-1]+1);			lenx[++cntx] = 1;			Pos[i] = cntx;//bad coconuts所在的段數(shù)		}		for(int i=0; i<Q; i++)		{			int t = lower_bound(temp,temp+index,x[i])-temp;			x[i] = Pos[t];//離散后更新原坐標(biāo)		}		//離散化y軸		index = 0;		temp[index++] = 0;		temp[index++] = C;		for(int i=0; i<Q; i++)			temp[index++] = y[i];		sort(temp, temp+index);		index = unique(temp, temp+index)-temp;		cnty = 0;		for(int i=1; i<index; i++)		{			if(temp[i] > temp[i-1]+1)				leny[++cnty] = temp[i]-(temp[i-1]+1);			leny[++cnty] = 1;			Pos[i] = cnty;		}		for(int i=0; i<Q; i++)		{			int t = lower_bound(temp, temp+index, y[i])-temp;			y[i] = Pos[t];		}		//DFS		memset(book, false, sizeof(book));		for(int i=0; i<Q; i++)			book[x[i]][y[i]] = true;		for(int i=1; i<=cntx; i++)			for(int j=1; j<=cnty; j++)				if(!book[i][j])					Area.push_back(dfs(i, j));		//output		sort(Area.begin(), Area.end());		int len = (int)Area.size();		cout<<"Case #"<<(Case++)<<":/n"<<len<<"/n";		for(int i=0; i<len-1; i++)			cout<<Area[i]<<" ";		cout<<Area[len-1]<<endl;	}}