AcWing每日一题(提高组)--星空之夜

https://www.acwing.com/problem/content/1404/

考察flood fill 和图的hash。

这题有两问：1、找出图中的全部连通块

　　　　　　2、根据形状给给将相似的连通块换上同一个字符

对于第一问，可以直接应用flood fill算法。

对于第二问，我们可以通过hash的方式辨别不同的连通块，我们需要保证相似的连通块的hash值相同，不相似的连通块的hash值尽量不同。

通过观察可以发现，假设两个连通块相似，构成这个连通块的两两之间的距离的和是相等的，故可依此对连通块进行hash。

（在考试的时候，对于字符串和树图的hash一定不要去处理冲突，因为如果处理冲突，那么hash的意义也就不存在了，如果冲突就在写一个hash函数）

 1 #include<iostream>
 2 #include<cmath>
 3 using namespace std;
 4 const int N=110;
 5 const double eps=1e-6;
 6 typedef pair<int,int> PII;
 7 int n,m;
 8 char g[N][N];
 9 PII locate[N*N];
10 int cnt=0;
11 double get_dist(PII a,PII b){//获得两点之间的距离
12     double x=a.first-b.first;
13     double y=a.second-b.second;
14     return sqrt(x*x+y*y);
15 }
16 double get_hash(){//获得当前连通块的hash值
17     double sum=0;
18     for(int i=0;i<cnt;i++){
19         for(int j=i+1;j<cnt;j++){
20             sum+=get_dist(locate[i],locate[j]);
21         }
22     }
23     return sum;
24 }
25 char get_id(double hash){//找到hash值对应的字母
26     static double mp[40];
27     static int id=0;
28     for(int i=0;i<id;i++){
29         if(fabs(hash-mp[i])<eps){
30             return 'a'+i;
31         }
32     }
33     mp[id]=hash;
34     return 'a'+id++;
35 }
36 void dfs(int a,int b){//flood fill
37     int u[]={-1,-1,-1,0,1,1,1,0};
38     int v[]={-1,0,1,1,1,0,-1,-1};
39     locate[cnt++]={a,b};
40     g[a][b]='0';
41     for(int i=0;i<8;i++){
42         int x=a+u[i],y=b+v[i];
43         if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]=='1'){
44             dfs(x,y);
45         }
46     }
47 }
48 int main(void){
49     cin>>m>>n;
50     for(int i=0;i<n;i++){
51         cin>>g[i];
52     }
53     for(int i=0;i<n;i++){
54         for(int j=0;j<m;j++){
55             if(g[i][j]=='1'){
56                 cnt=0;
57                 dfs(i,j);
58                 char c=get_id(get_hash());
59                 for(int k=0;k<cnt;k++){
60                     g[locate[k].first][locate[k].second]=c;
61                 }
62             }
63         }
64     }
65     for(int i=0;i<n;i++) cout<<g[i]<<endl;
66     return 0;
67 }