PKU 1175 Starry Night
http://poj.org/problem?id=1175
h*wのマスが与えられる。この中で回転や反転させて同じ形になる1の塊に、見つかった順に固有のアルファベットを割り当てろというような問題。
サイズが大きいような気がしましたが、statusを見てもほとんど一瞬で終わっている人がほとんどなので、贅沢に行かせてもらいました。
string in[100]; bool vis[100][100]; map<vector<PI>,char> app; char getnum(vector<PI> in){ rep(j,2){ FOR(it,in)*it=mp(it->S,it->F); rep(i,4){ FOR(it,in) *it=mp(-it->S,it->F); PI me=*min_element(ALL(in)); FOR(it,in){ it->F-=me.F; it->S-=me.S; } sort(ALL(in)); if(app.count(in))return app[in]; } } int ret=SZ(app); return app[in]=ret+'a'; } main(){ int w,h; cin>>w>>h; rep(i,h)cin>>in[i]; rep(i,h)rep(j,w){ if(in[i][j]!='1')continue; queue<PI>q; vector<PI>clu; q.push(mp(i,j)); while(!q.empty()){ int cx=q.front().F,cy=q.front().S; q.pop(); if(vis[cx][cy])continue; vis[cx][cy]=true; clu.pb(mp(cx,cy)); rep(i,8){ int nx=cx+dx[i],ny=cy+dy[i]; if(nx<0 || h<=nx || ny<0 || w<=ny || vis[nx][ny] || in[nx][ny]!='1')continue; q.push(mp(nx,ny)); } } char c=getnum(clu); rep(k,SZ(clu))in[clu[k].F][clu[k].S]=c; } rep(i,h)cout<<in[i]<<endl; }