POJ 1175

  1 //本来写了个和1021相同的HASH，但没过，于是，抱着侥幸的心理，把它变成距离的四次方，
  2 //我就呵呵了。。。
  3 //这个题，完全靠概率。当然了，如果是把图翻转来比较，也是可以的。但好像很麻烦。。 
  4 
  5 #include <iostream>
  6 #include <cstdio>
  7 #include <cstring>
  8 
  9 using namespace std;
 10 const int MAX=105;
 11 const int MOD=1500;
 12 char map[MAX][MAX];
 13 int dir[8][2]={1,0,-1,0,0,1,0,-1,1,1,1,-1,-1,1,-1,-1};
 14 int w,h;
 15 struct cl{
 16     char c;
 17     int val,next;
 18 }clu[600];
 19 int hash[1500];
 20 struct sv{
 21     int x,y;
 22 }save[200];
 23 int sa,counted;
 24 int tot;
 25 void dfs(int i,int j){
 26     map[i][j]='0'; sa++;
 27     save[sa].x=i; save[sa].y=j;
 28     for(int k=0;k<7;k++){
 29         int tx=i+dir[k][0];
 30         int ty=j+dir[k][1];
 31         if(map[tx][ty]=='1'&&tx>=0&&tx<h&&ty>=0&&ty<w){
 32             dfs(tx,ty);
 33         }
 34     }
 35 }
 36 
 37 void calculate(){
 38     int i,j,x,y;
 39     int sum=0;
 40     for(i=1;i<=sa;i++){
 41         x=save[i].x; y=save[i].y;
 42         for(j=i+1;j<=sa;j++){
 43             int dx=abs(x-save[j].x);
 44             int dy=abs(y-save[j].y);
 45             sum=sum+(dx*dx+dy*dy)*(dx*dx+dy*dy);
 46         }
 47     }
 48     int h=sum%MOD; char sure;
 49     if(hash[h]==-1){
 50         sure='a'+(++counted);
 51         clu[tot].val=sum;
 52         clu[tot].c=sure;
 53         clu[tot].next=hash[h];
 54         hash[h]=tot++;
 55     }
 56     else{
 57     //    bool flag=false;
 58         for(int e=hash[h];e!=-1;e=clu[e].next){
 59             if(clu[e].val==sum){
 60                 clu[tot].c=clu[e].c;
 61                 clu[tot].val=sum;
 62                 clu[tot].next=hash[h];
 63                 hash[h]=tot++;
 64                 sure=clu[e].c;
 65             //    flag=true;
 66                 break;
 67             }
 68         }
 69     }
 70     for(i=1;i<=sa;i++){
 71         map[save[i].x][save[i].y]=sure;
 72     }
 73 }
 74 
 75 void slove(){
 76     for(int i=0;i<h;i++){
 77         for(int j=0;j<w;j++){
 78             if(map[i][j]=='1'){
 79                 sa=0;
 80                 dfs(i,j);
 81                 calculate();
 82             }
 83         }
 84     }
 85 }
 86 
 87 int main(){
 88     int i;
 89     while(scanf("%d%d",&w,&h)!=EOF){
 90         for(i=0;i<h;i++)
 91         scanf("%s",map[i]);
 92         counted=-1; tot=0;
 93         memset(hash,-1,sizeof(hash));
 94         slove();
 95         for(i=0;i<h;i++){
 96         printf("%s",map[i]);
 97         printf("
");
 98         }
 99     }
100     return 0;
101 }
View Code