已根据y总视频讲解注释每一行code的含义。
核心算法即:(近似算法)哈希:每一个点之间距离之和。假设这个是唯一的。
(数据水的时候这样就可以,绝大多数平台都能过,如果过不了再加入新的哈希,使得错误率/冲突率低到很小,(比如一种哈希错误率1%,两种独立哈希就(按概率公式得)0.01%,如果有相关性那>0.01%不过也应比1%小)应用到小数据时= 0)
c++ y总代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
const double eps = 1e-6;
int n, m;
char g[N][N]; //地图用g来表示
PII q[N * N]; //连通块, 每个块里点数是n^2.
int top; //当前块里有多少个点
double get_dist(PII a, PII b) //两点间距离
{
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx*dx + dy*dy);
}
double get_hash()
{
double sum = 0;
for (int i = 0; i < top; i++)
for (int j = i + 1; j < top; j++) //枚举每两个点
sum += get_dist(q[i], q[j]); //之间的距离是多少,并加入sum总和中
return sum;
}
char get_id(double key)
{
static double hash[30]; //静态,全局变量,一共26个英文字母,所以大小开30即可
static int id = 0;
for (int i = 0; i < id; i++)
if (fabs(hash[i] - key) < eps) //判断两个浮点数是否相等,这种方法可以忽略计算机的浮点误差
return i + 'a'; //前面出现过k的话,就返回第i项字母
hash[id ++] = key; //(没出现过的话),把k存下来
return id - 1 + 'a'; //注:[个人理解]:上一行id++了 这里就-1减回来,然后+'a'是因为cpp特性,新循环时就变b, c, d...等等 注意这里是没出现过才会加,因为上面判断了如果出现过就先return i+ 'a'了
//2022update:应该不只是cpp,只是'a'对应ASCII码:97 然后加一了就是'b', 以此类推.
}
void dfs(int a, int b) //实现FloodFills 算法
{
q[top ++] = {a, b}; //①将当前点存下来
g[a][b] = '0'; //②标记当前点已被走过
for (int x = a - 1; x <= a + 1; x++) //枚举{a, b}的所有邻点
for (int y = b - 1; y <= b + 1; y++)
{
if (x == a && y ==b) continue; //中心点跳过
if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '1') //没出界限的话 + 还没走过
dfs(x, y);
}
}
int main()
{
cin >> m >> n; // 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 c = get_id(get_hash()); //找到当前连通块的id ,通过哈希值
for (int k = 0; k < top; k++) //把当前所有连通块里的点
g[q[k].x][q[k].y] = c; //标记为c
}
for (int i = 0; i < n; i++) cout << g[i] << endl;
return 0;
}
讲道理对于我这种新手我感觉每一个题解都需要到这个深度hh 保证每一句都能看懂,新的一年自己也要认真跟着视频写注释!
加油!希望可以坚持下来写题解
写的挺好的,代码恨易懂。
我尼玛刀!
没懂
get_id
的意思妙妙种子
不使用static,用全局变量为啥不行
我也想问,知道了踢我一下
只能是你用错了
不懂
OTZ大佬
大神!i了i了!AI卷起来!
好东西,你要坚持下去,坚持哈哈
太屌了