记录编号	196075	评测结果	AAAAA
题目名称	897.夜空繁星	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.326 s
提交时间	2015-10-20 19:54:58	内存使用	0.73 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
const int SIZEN=110,INF=0x7fffffff/2;
class miku
{
    public:
	int xd,yd;
	int temx,temy,temxx,temyy;
	bool M[SIZEN][SIZEN];
	void clear()
	{
		temxx=temyy=0;
		temx=temy=INF;
		memset(M,0,sizeof(M));
	}
	void push(int x,int y)
	{
		temx=min(temx,x);temy=min(temy,y);temxx=max(temxx,x);temyy=max(temyy,y);
		M[x][y]=1;
	}
	bool bj(miku A)
	{
		if(xd!=A.xd||yd!=A.yd) return 0;
		for(int i=1;i<=xd;i++)
			for(int j=1;j<=yd;j++)
				if(M[i][j]!=A.M[i][j]) return 0;
		return 1;
	}
	void print()
	{
		cout<<xd<<" "<<yd<<endl;
		for(int i=1;i<=xd;i++)
		{
			for(int j=1;j<=yd;j++)
				cout<<M[i][j];
			cout<<endl;
		}
	}
}P[30];
int N,w;
bool mp[SIZEN][SIZEN]={0};
int cnt=0;
int co[SIZEN][SIZEN]={0};
int dx[]={0,0,-1,1,-1,1,-1,1};
int dy[]={1,-1,-1,1,1,-1,0,0};
miku A;
void read()
{
	scanf("%d",&w);
	scanf("%d",&N);
	char str[SIZEN];
	for(int i=1;i<=N;i++)
	{
		scanf("%s",str);
		for(int j=1;j<=w;j++) mp[i][j]=str[j-1]-'0';
	}
}
void dfs(int x,int y)
{
	A.push(x,y);
	co[x][y]=INF;
	for(int i=0;i<8;i++)
	{
		int temx=x+dx[i],temy=y+dy[i];
		if(!co[temx][temy]&&mp[temx][temy])
			dfs(temx,temy);
	}
}
miku turn90(miku T)
{
	miku ans;
	ans.clear();
	ans.xd=T.yd;
	ans.yd=T.xd;
	for(int i=1;i<=ans.xd;i++)
	{
		for(int j=1,k=T.xd;j<=N;j++,k--) ans.M[i][j]=T.M[k][i];
	}
	return ans;
}
miku obsertive(miku T)
{
	miku ans;
	ans.xd=T.xd;
	ans.yd=T.yd;
	for(int i=1;i<=ans.xd;i++)
		for(int j=1,k=T.yd;j<=ans.yd;j++,k--) ans.M[i][j]=T.M[i][k];
	return ans;
}
miku make(miku A)
{
	miku ans;
	ans.clear();
	ans.xd=A.temxx-A.temx+1;ans.yd=A.temyy-A.temy+1;
	for(int i=1,k=A.temx;i<=ans.xd;i++,k++)
		for(int j=1,p=A.temy;j<=ans.yd;j++,p++)
		{
			ans.M[i][j]=A.M[k][p];
		}
	return ans;
}
bool check(miku A,miku B)
{
	miku T=A;
	if(T.bj(B)) return 1;
    T=turn90(T);if(T.bj(B)) return 1;	
	T=turn90(T);if(T.bj(B)) return 1;	
	T=turn90(T);if(T.bj(B)) return 1;
	T=obsertive(A);if(T.bj(B)) return 1;
	T=turn90(T);if(T.bj(B)) return 1;	
	T=turn90(T);if(T.bj(B)) return 1;	
	T=turn90(T);if(T.bj(B)) return 1;
	return 0;
}
int pan(miku A)
{
	for(int i=1;i<=cnt;i++) 
		if(check(P[i],A)) return i;
	return 0;
}
void dfs2(int x,int y,int c)
{
	co[x][y]=c;
	for(int i=0;i<8;i++)
	{
		int temx=x+dx[i],temy=y+dy[i];
		if(co[temx][temy]==INF)
			dfs2(temx,temy,c);
	}
}
void work()
{
	for(int i=1;i<=26;i++) P[i].clear();
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=w;j++)
			if(mp[i][j]&&!co[i][j])
			{
				A.clear();
				dfs(i,j);
				A=make(A);
				//cout<<"i:"<<i<<" "<<"j:"<<j<<endl;
				//A.print();
				int tem=pan(A);
				if(!tem)
				{
					cnt++;
					P[cnt]=A;
					dfs2(i,j,cnt);
				}
				else dfs2(i,j,tem);
				
			}
	}
}
void out()
{
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=w;j++)
		{
			if(!co[i][j]) printf("0");
			else
			{
				char c='a'+co[i][j]-1;
				printf("%c",c);
			}
		}
		printf("\n");
	}
}
int main()
{
	freopen("starry.in","r",stdin);
	freopen("starry.out","w",stdout);
	read();
	work();
	out();
	return 0;
}