记录编号 | 196075 | 评测结果 | AAAAA | ||
---|---|---|---|---|---|
题目名称 | 夜空繁星 | 最终得分 | 100 | ||
用户昵称 | 是否通过 | 通过 | |||
代码语言 | 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; }