题目描述

因为又加入了新的测试点（y总又偷偷的加了一次），所以y总讲的两种哈希方法已经被干掉了。
（一个是累计两点间距离和，一个是计算每个点到中心的距离和）
不过就算是这两个哈希方式加在一起都无法通过啊。样例我放下面了，感兴趣的小伙伴可以去想一想还有什么模糊匹配的哈希能够避开这种冲突。

话归正题啊，因为模糊哈希没办法通过了，所以我写了一个暴力匹配的写法。代码思路来自某位前辈啊，我觉得思路很优雅所以就发出来了。

样例

1100110
0100010
1100011
1110111
0010001

算法

#include<iostream>
#include<map>
#include<algorithm>
#include<vector>
#define s second
#define f first
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
int n, m;
char mp[N][N];
bool st[N][N]; //存储每个位置有没有被读到
PII s[] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}, {-1, 1}, {-1, -1}, {1, -1}, {1, 1}};
map<vector<PII>, char> umap;

void dfs(int x, int y, vector<PII>& vtr) //dfs取出连通块
{
    st[x][y] = true;
    vtr.push_back({x, y});
    for(int i = 0; i < 8; i++)
    {
        int dx = x + s[i].f, dy = y + s[i].s;
        if(!st[dx][dy] && mp[dx][dy] == '1')
            dfs(dx, dy, vtr);
    }
}

vector<PII> swap_matrix(vector<PII>& vtr, int r) //翻转矩阵
{
    PII s[] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
    vector<PII> swp;
    for(auto [x, y] : vtr)
    {
        if(r > 3) swap(x, y); //翻转后进行
        swp.push_back({x * s[r % 4].f, y * s[r % 4].s});
    }
    return swp;
}

vector<PII> get_hash(vector<PII>& vtr) //构造哈希
{
    vector<vector<PII>> vtt;
    for(int r = 0; r < 8; r++) //8个方向
    {
        vector<PII> swp = swap_matrix(vtr, r);
        sort(swp.begin(), swp.end());
        int mxx = 1e9, mxy = 1e9;
        for(auto [x, y] : swp)
            mxx = min(mxx, x), mxy = min(mxy, y); //取最小值
        for(int i = 0; i < swp.size(); i++)
            swp[i].f -= mxx, swp[i].s -= mxy; //取相对坐标
        vtt.push_back(swp); //加入函数值
    }
    sort(vtt.begin(), vtt.end());
    return vtt[0]; //将首位作为哈希值
}

void solve()
{
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= n; i++)
        scanf("%s", mp[i] + 1); //读取地图
    char a = 'a';
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(mp[i][j] == '1' && !st[i][j])
            {
                vector<PII> vtr;
                dfs(i, j, vtr);
                vector<PII> hash = get_hash(vtr); //获取哈希值
                if(umap.find(hash) == umap.end())
                    umap[hash] = a++;
                char l = umap[hash];
                for(auto [x, y] : vtr)
                    mp[x][y] = l;
            }
        }
    }
    for(int i = 1; i <= n; i++)
        printf("%s\n", mp[i] + 1);
}
int main()
{
    solve();
    return 0;
}