AcWing 每日一题打卡（1）——1402. 星空之夜

dfs求连通块 通过连通块内距离和来判断是否是同一个形状。

#include<bits/stdc++.h>
#define PII pair<int, int> 
#define x first
#define y second
using namespace std;

const int N = 110;

char mp[N][N];
int n,m;
int dir[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
vector<PII> v;
vector<PII> :: iterator it1, it2;
char star = 'a';
map<double, char> name;

double getdis(PII a, PII b){
    double xx = a.x - b.x, yy = a.y - b.y;
    return sqrt(xx * xx + yy * yy);
}

void distribute_name(){
    double sum = 0.0, eps = 1e-6;
    for(it1 = v.begin(); it1 != v.end(); ++ it1)
        for(it2 = it1 + 1; it2 != v.end(); ++ it2)
            sum += getdis(*it1, *it2);
    char s = '$';
    for(auto u : name){
        if(abs(u.x - sum) < eps){
            s = u.y;
            break;
        }
    }
    if(s == '$')    s = star ++, name[sum] = s;
    for(auto u : v) mp[u.x][u.y] = s;
    v.clear();
}

void dfs(int x, int y){
    mp[x][y] = '0';
    v.push_back({x, y});
    for(int k = 0; k < 8; ++ k){
        int tx = x + dir[k][0], ty = y + dir[k][1];
        if(tx < 1 || ty < 1 || tx > n || ty > m || mp[tx][ty] == '0')    continue;
        dfs(tx, ty);
    }
}

int main(){
    cin >> m >> n;
    for(int i = 1; i <= n; ++ i){
        getchar();
        for(int j = 1; j <= m; ++ j)
            scanf("%c", &mp[i][j]);
    }
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= m; ++ j)
            if(mp[i][j] == '1'){
                dfs(i, j);
                distribute_name();
            }
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= m; ++ j)
            printf("%c", mp[i][j]);
        putchar('\n');
    }
    return 0;
}