记录编号	81472	评测结果	AAAAA
题目名称	夜空繁星	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.151 s
提交时间	2013-11-13 21:02:32	内存使用	0.29 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<vector>
#include<cstring>
using namespace std;
const int SIZEW=101;
const int SIZEN=501;
const int INF=0x7fffffff;
bool board[SIZEW][SIZEW]={0};
bool flag[SIZEW][SIZEW]={0};
int dx[]={0,0,0,-1,-1,-1,1,1,1};
int dy[]={0,1,-1,-1,0,1,-1,0,1};
int W,H;//H是行数,W是列数
void print(char s[SIZEW][SIZEW]){
	int i,j;
	for(i=1;i<=H;i++){
		for(j=1;j<=W;j++) printf("%c",s[i][j]);
		printf("\n");
	}
}
class POINT{//在本题中,x代表行坐标,y代表列坐标,与数学相反
public:
	int x,y;
};
bool operator != (POINT a,POINT b){
	return a.x!=b.x||a.y!=b.y;
}
bool operator < (POINT a,POINT b){//x为第一关键字,y为第二关键字
	if(a.x<b.x) return true;
	if(a.x>b.x) return false;
	return a.y<b.y;
}
class GALAXY{//不要吐槽翻译
public:
	int w,h;//w是宽度,h是高度
	int minx,miny,maxx,maxy;//刚好包裹整个星座的矩形,并非坐标最小/大的星体
	set<POINT> stars;//包含星体数为stars.size(),这里储存的是减去minx,miny之后的"偏移坐标"
	char mark;
	GALAXY(){
		minx=miny=INF;
		maxx=maxy=0;
		mark=0;
		stars.clear();
	}
	void floodfill(int,int);
	void getmember(int,int);
	void markboard(char[SIZEW][SIZEW]);
	void output(void){
		char tp[SIZEW][SIZEW]={0};
		bool flag=false;
		if(minx==INF){
			flag=true;
			minx=miny=1;
			maxx=h,maxy=w;
		}
		markboard(tp);
		int i,j;
		cout<<"galaxy:"<<endl;
		cout<<w<<" "<<h<<" "<<mark<<endl;
		for(i=minx;i<=maxx;i++){
			for(j=miny;j<=maxy;j++){
				cout<<(tp[i][j]?tp[i][j]:' ');
			}
			cout<<endl;
		}
		cout<<endl<<endl<<endl;
		if(flag) minx=miny=INF,maxx=maxy=0;
	}
	void outset(void){
		set<POINT>::iterator key;
		for(key=stars.begin();key!=stars.end();key++) cout<<(key->x)<<" "<<(key->y)<<endl;
		cout<<endl;
	}
};
bool operator == (GALAXY a,GALAXY b){//经平移后可以重叠
	if(a.w!=b.w) return false;
	if(a.h!=b.h) return false;
	if(a.stars.size()!=b.stars.size()) return false;
	set<POINT>::iterator key1,key2;
	for(key1=a.stars.begin(),key2=b.stars.begin();key1!=a.stars.end();key1++,key2++) if((*key1)!=(*key2)) return false;
	return true;
}
void GALAXY::markboard(char bd[SIZEW][SIZEW]){
	set<POINT>::iterator key;
	for(key=stars.begin();key!=stars.end();key++){
		bd[minx+key->x][miny+key->y]=mark;
	}
}
void GALAXY::floodfill(int nowx,int nowy){
	if(flag[nowx][nowy]) return;
	flag[nowx][nowy]=true;
	minx=min(minx,nowx),miny=min(miny,nowy);
	maxx=max(maxx,nowx),maxy=max(maxy,nowy);
	stars.insert((POINT){nowx,nowy});
	int nextx,nexty;
	int i;
	for(i=1;i<=8;i++){
		nextx=nowx+dx[i];
		nexty=nowy+dy[i];
		if(1<=nextx&&nextx<=H&&1<=nexty&&nexty<=W&&board[nextx][nexty]) floodfill(nextx,nexty);
	}
}
void GALAXY::getmember(int nowx,int nowy){
	floodfill(nowx,nowy);
	w=maxy-miny+1,h=maxx-minx+1;
	set<POINT>::iterator key;
	POINT temp;
	vector<POINT> tp;
	int i;
	for(key=stars.begin();key!=stars.end();key++) tp.push_back((POINT){(key->x)-minx,(key->y)-miny});
	stars.clear();
	for(i=0;i<tp.size();i++) stars.insert(tp[i]);
}
GALAXY turnac(GALAXY &g){//将g逆时针旋转90度,但矩形四角坐标为构造函数值
	GALAXY ans;
	ans.w=g.h;
	ans.h=g.w;
	ans.mark=g.mark;
	set<POINT>::iterator key;
	for(key=g.stars.begin();key!=g.stars.end();key++){
		ans.stars.insert((POINT){g.w-1-(key->y),(key->x)});
	}
	return ans;
}
GALAXY reversal(GALAXY &g){//将g左右翻转,但矩形四角坐标为构造函数值
	GALAXY ans;
	ans.w=g.w;
	ans.h=g.h;
	ans.mark=g.mark;
	set<POINT>::iterator key;
	for(key=g.stars.begin();key!=g.stars.end();key++) ans.stars.insert((POINT){(key->x),g.w-1-(key->y)});
	return ans;
}
GALAXY gals[SIZEN];
int n;
char ansboard[SIZEW][SIZEW]={0};
void markboard(void){
	int i,j;
	for(i=1;i<=H;i++){
		for(j=1;j<=W;j++) ansboard[i][j]='0';
	}
	for(i=1;i<=n;i++) gals[i].markboard(ansboard);
}
void get_similar(int x){//给与gals[x]相似的天体标号
	vector<GALAXY> nowg;
	GALAXY temp;
	temp=gals[x];
	nowg.push_back(temp);//原先
	temp=turnac(temp);
	nowg.push_back(temp);//转一次
	temp=turnac(temp);
	nowg.push_back(temp);//转两次
	temp=turnac(temp);
	nowg.push_back(temp);//转三次
	temp=reversal(gals[x]);//翻转
	nowg.push_back(temp);
	temp=turnac(temp);
	nowg.push_back(temp);//翻转转一次
	temp=turnac(temp);
	nowg.push_back(temp);//转两次
	temp=turnac(temp);
	nowg.push_back(temp);//转三次
	int i,j;
	for(i=x+1;i<=n;i++){
		for(j=0;j<nowg.size();j++){
			if(gals[i]==nowg[j]){
				gals[i].mark=gals[x].mark;
				break;
			}
		}
	}
}
void mark_similar(void){
	char ch='a';
	int i;
	for(i=1;i<=n;i++){
		if(gals[i].mark==0){
			gals[i].mark=ch++;
			get_similar(i);
		}
	}
}
void getgalaxy(void){
	int i,j;
	n=0;
	for(i=1;i<=H;i++){
		for(j=1;j<=W;j++){
			if(board[i][j]&&!flag[i][j]) gals[++n].getmember(i,j);
		}
	}
}
void read(void){
	scanf("%d%d",&W,&H);
	int i,j;
	char ch;
	string str;
	for(i=1;i<=H;i++){
		cin>>str;
		for(j=1;j<=W;j++){
			ch=str[j-1];
			board[i][j]=ch-'0';
		}
	}
}
int main(){
	freopen("starry.in","r",stdin);
	freopen("starry.out","w",stdout);
	read();
	getgalaxy();
	mark_similar();
	markboard();
	print(ansboard);
	int x=2;
	gals[x].mark='a';
	reversal(gals[x]);
	return 0;
}