TZOJ5113:StarryNight

#include
using namespace std;
int w,h;
int up,l;
int bottom,r;
struct point{
int x,y;
};
char s[105][105],f[505];
bool vis[105][105];
vector v[505],vk[505];
int dtx[]={-1,-1,-1,0,0,1,1,1};
int dty[]={0,1,-1,1,-1,1,0,-1};
bool check(int x,int y){
if(x<0||x>=h||y<0||y>=w)return false;
return true;
}
void bfs(int x,int y,int id){
queue q;
l=w;
up=h;
q.push((point){x,y});
vis[x][y]=1;
while(!q.empty()){
point u=q.front();
v[id].push_back(u);
q.pop();
l=min(l,u.y);
up=min(up,u.x);
for(int i=0;i<8;i++){
point v=u;
v.x+=dtx[i];
v.y+=dty[i];
if(!check(x,y))continue;
if(vis[v.x][v.y]==0&&s[v.x][v.y]==‘1‘){
q.push(v);
vis[v.x][v.y]=1;
}
}
}
}
void get_vk(int id){
for(int i=0;i){
vk[id].push_back((point){v[id][i].x-up,v[id][i].y-l});
}
}
bool cmp(point a,point b){
return a.xb.y;
}
bool check_equal(vector a,vector b){
sort(a.begin(),a.end(),cmp);
sort(b.begin(),b.end(),cmp);
for(int i=0;i){
if(a[i].x!=b[i].x||a[i].y!=b[i].y)
return false;
}
return true;
}
void set_data(vector &a){//获得图形的边界
bottom=-1,r=-1;
for(int i=0;i){
bottom=max(a[i].x,bottom);
r=max(a[i].y,r);
}
}
void Reverse(vector &a){ //左右翻转
set_data(a);
for(int i=0;i){
a[i].y=(r-a[i].y);
}
}
void spin(vector &a){//逆时针旋转
set_data(a);
for(int i=0;i){
int z=a[i].y;
a[i].y=a[i].x;
a[i].x=(r-z);
}
}
/*/char shape[105][105];
void out_shape(vector &a){
set_data(a);
for(int i=0;i<=bottom;i++)
for(int j=0;j<=r;j++)
shape[i][j]=‘0‘;
for(int i=0;i shape[a[i].x][a[i].y]=‘1‘;
}
printf("%d\n",a.size());
for(int i=0;i<=bottom;i++)
{for(int j=0;j<=r;j++)
printf("%c",shape[i][j]);
printf("\n");
}
printf("\n");
}/*/
bool judge(int x,int y){//判断两个图形是否相似
vector vr,vt;
vr=vk[x];vt=vk[y];
for(int i=1;i<=4;i++){
spin(vr);
//out_shape(vr);
if(check_equal(vr,vt))return true;
Reverse(vr);
//out_shape(vr);
if(check_equal(vr,vt))return true;
Reverse(vr);
//out_shape(vr);
}
return false;
}
int main(){
scanf("%d%d",&w,&h);
for(int i=0;i){
scanf("%s",s[i]);
}
int k=0;
for(int i=0;i){
for(int j=0;j){
if(s[i][j]==‘1‘&&vis[i][j]==0){
bfs(i,j,++k);//bfs 查找连通块
get_vk(k); //图像左移上移
}
}
}
char ch=‘a‘;
f[1]=‘a‘; //第一个连通块为a
for(int i=2;i<=k;i++){
int flag=0;
for(int j=1;j//和已判断连通块进行比较
if(vk[i].size()!=vk[j].size())continue;//点数不同直接跳过
if(judge(i,j)){ //图像相似
flag=1;
f[i]=f[j];
break;
}
}
if(!flag)f[i]=++ch;//未有相似图像，新增图像字符
}
for(int i=1;i<=k;i++){
for(int j=0;j){
s[v[i][j].x][v[i][j].y]=f[i];
}
} //字符设置
for(int i=0;i){
printf("%s\n",s[i]);
}
}