FloodFill遍历，对于个每个图形，分别进行旋转、对称total7种操作，然后在hash table中找是否存在。
/**//*
ID: lorelei3
TASK: starry
LANG: C++
*/
#include <fstream>
#include <queue>
#include <memory.h>
using namespace std;
const int MAX = 105;
const int MAXT = 505;
const int dx[] =
{1,1,0,-1,-1,-1, 0, 1};
const int dy[] ={0,1,1, 1, 0,-1,-1,-1};
const int INF = 0x7FFFFFF;
struct Point{
int x,y;
};
struct Hashcode{
int width,height;
char mark;
bool code[MAX][MAX];
Hashcode(){
memset(code, false, sizeof(code));
}
};
ifstream fin("starry.in");
ofstream fout("starry.out");
char map[MAX][MAX];
char newmark = 'a';
int cnt;
Hashcode ht[MAXT];
int w,h;
void input(){
fin>>w>>h;
fin.get();
for(int i=0; i<h; ++i){
for(int j=0; j<w; ++j){
map[i][j] = (char)fin.get();
}
fin.get();
}
}
void flip(const Hashcode in, Hashcode &out){
out.height = in.height;
out.width = in.width;
out.mark = in.mark;
for(int i=0; i<in.width; ++i)
for(int j=0; j<in.height; ++j)
out.code[i][in.height-1-j]=in.code[i][j];
}
void turn(const Hashcode in, Hashcode &out){
out.height=in.width;
out.width=in.height;
out.mark = in.mark;
for(int i=0; i<in.width; ++i)
for(int j=0; j<in.height; ++j)
out.code[j][in.width-1-i]=in.code[i][j];
}
void transform(const Hashcode in, Hashcode &out, int op){
if(op==0){
out = in;
return;
}
if(op==1){
turn(in, out);
return;
}
if(op==2){
Hashcode t;
turn(in, t);
turn(t, out);
return;
}
if(op==3){
Hashcode t1,t2;
turn(in, t1);
turn(t1, t2);
turn(t2, out);
return;
}
if(op==4){
flip(in, out);
return;
}
if(op==5){
Hashcode t;
flip(in, t);
turn(t, out);
}
if(op==6){
Hashcode t1,t2;
flip(in, t1);
turn(t1, t2);
turn(t2, out);
}
if(op==7){
Hashcode t1,t2,t3;
flip(in, t1);
turn(t1, t2);
turn(t2, t3);
turn(t3, out);
}
}
int findhash(Hashcode code){
for(int k=0; k<cnt; ++k){
if(code.height!=ht[k].height || code.width!=ht[k].width)
continue;
bool flag = true;
for(int i=0; i<code.width; ++i)
for(int j=0; j<code.height; ++j)
if(code.code[i][j] != ht[k].code[i][j]){
flag = false;
break;
}
if(flag==true)
return k;
}
return -1;
}
void floodfill(int x, int y){
int i,j, ii, jj;
Point st;
st.x = x, st.y =y;
int minx=INF, miny=INF, maxx=0, maxy=0;
queue<Point> Q;
Q.push(st);
while(!Q.empty()){
Point pt = Q.front();
Q.pop();
map[pt.x][pt.y]='2';
if(pt.x<minx) minx=pt.x;
if(pt.x>maxx) maxx=pt.x;
if(pt.y<miny) miny=pt.y;
if(pt.y>maxy) maxy=pt.y;
for(int i=0; i<8; ++i){
Point t;
t.x=pt.x+dx[i];
t.y=pt.y+dy[i];
if(t.x<0||t.x>h)continue;
if(t.y<0||t.y>w)continue;
if(map[t.x][t.y]=='1'){
map[t.x][t.y]='2';
Q.push(t);
}
}
}
Hashcode hash;
hash.width = maxx-minx+1;
hash.height = maxy-miny+1;
for(i=minx, ii=0; i<=maxx; ++i, ++ii)
for(j=miny, jj=0; j<=maxy; ++j,++jj)
if(map[i][j]=='2')
hash.code[ii][jj]=true;
else
hash.code[ii][jj]=false;
char mark=0;
for(int op=0; op<8; ++op){
Hashcode code;
transform(hash, code, op);
int k = findhash(code);
if(k!=-1){
mark = ht[k].mark;
break;
}
}
if(mark==0){
mark = (char)newmark++;
hash.mark = mark;
ht[cnt++]=hash;
}
for(i=minx; i<=maxx; ++i)
for(j=miny; j<=maxy; ++j)
if(map[i][j]=='2')
map[i][j]=mark;
}
void solve(){
for(int i=0; i<h; ++i)
for(int j=0; j<w; ++j)
if(map[i][j]=='1')
floodfill(i,j);
}
void output(){
for(int i=0; i<h; ++i){
for(int j=0; j<w; ++j)
fout<<map[i][j];
fout<<endl;
}
}
int main(){
input();
solve();
output();
return 0;
}
posted on 2011-02-08 13:01
小阮 阅读(319)
评论(0) 编辑 收藏 引用 所属分类:
USACO