ReMind

Recent Writing

See 247 more →

星空之夜

4 min read

原题链接：1402. 星空之夜 - AcWing题库

题意：给定连通块，说一种连通块有多个形态，只要形状一样就认为是一种，在给定的矩阵中用字典序依次代替连通块，同一种用同一个字符

思路

首先是连通块的遍历——Foold Fill(DFS / BFS)

解决连通块遍历后，要解决怎么认识连通块是同一个形状

  • 考虑遍历，遍历到一个连通块就将其各个旋转角度存在字典里，每次找到新的连通块就查找字典

    时间复杂度勉强过得去，但是实现比较繁杂，实际上没有自信

  • 联想到哈希表，哈希表是通过每个数据赋予不同的哈希值来快速查找数据的，有无可能将一类形状记录到哈希表中呢？

    要解决同类形状的 共同点 问题（写的时候没想到） 用每个点的欧氏距离和，即直线距离之和

    设想同样形状可能点的坐标关系各不相同，但是点与点的距离一定一致，但是要注意的是这并非一定，不能完全通过每个点的距离之和就可以明确确定一个形状，可能有同距离和但是形状不同的情况出现，但是几率很低

    假设不开方再求和就不行，相同的几率大

实现

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
 
using namespace std;
 
typedef pair<int, int> PII;
 
const int N = 110, M = 170;
const double eps = 1e-8;
 
char g[N][N];
double hashs[30];
PII q[M];
int top, cnt;
int n, m;
 
//Foold fill遍历连通块，压栈用于改值
void dfs(int a, int b)
{
    q[top ++] = {a, b};
    g[a][b] = '0';
    
    for(int i = a - 1; i <= a + 1; i ++)
        for(int j = b - 1; j <= b + 1; j ++)
            if(i >= 0 && i < n && j < m && j >= 0 && g[i][j] == '1')
                dfs(i, j);
                
}
 
//计算哈希值
double get_hash()
{
    double sum = 0;
    for(int i = 0; i < top; i ++)
    {
        for(int j = 0; j < top; j ++)
        {
            double x = q[i].first - q[j].first;
            double y = q[i].second - q[j].second;
            
            sum += sqrt(x * x + y * y);
        }
    }
    
    return sum;
}
 
//查找字典
char get_char()
{
    double now_hash = get_hash();
    
    for(int i = 0; i < cnt; i ++)
        if(abs(now_hash - hashs[i]) < eps)
        {
            return 'a' + i;
        }
    
    hashs[cnt ++] = now_hash;
    return 'a' + cnt - 1;
}
 
 
int main()
{
    cin >> m >> n;
    
    for(int i = 0; i < n; i ++) cin >> g[i];
    
    for(int i = 0; i< n; i ++)
        for(int j = 0; j < m; j ++)
        {
            if(g[i][j] == '1')
            {
                top = 0;
                dfs(i, j);
                char idx = get_char();
                
                for(int i = 0; i < top; i ++)
                {
                    g[q[i].first][q[i].second] = idx;
                }
            }
        }
        
    
    for(int i = 0; i < n; i ++)
        puts(g[i]);
    
    return 0;
}

该题不止难在哈希算法的确定，还有实现上的问题

例如：将连通块的遍历的时候就标记查找过，同时又用一个数组记录下所有元素，用于后面计算hash值与改字符

事实证明这些实现方面需要加强

Graph View