思路
做了七八道联通的问题了,几乎都是用dfs做的,这里稍微总结一下。
板子写熟练了几乎就没什么问题了,题目变花样一般是要在dfs函数的开头和判断位置变一变;
至于一次dfs之后找到一个连通块之后,如何存连通块这个问题,有开辅助数组,用vector[HTML_REMOVED],用map 这几种方式,权衡一下就好,像这个题就是用了一个vector
这题还有一个很巧妙的地方在于判断相似,直接用内部块与块之间的距离,我第一次见,记住了,这种网格开double算sum dist判断同构。
这题还有个需要思考一下的地方在于算字母,我是把之前每个星群的sum dist都放在了一个map里(比放vector稍快),然后所有同构的星群就都是map::iterator->second对应的那个字母;如果有新的sum dist 就用mp.size() + ‘a’算一下。
这道题卡在了不会判断相似,以及判断完相似之后如何得到相同的字母,这中间的桥梁就是sum dist!!!!!!
万物皆想着用数字做映射。。。。。
C++ 代码
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath>
#include<map>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int m, n;
char g[N][N];
int dx[] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[] = {1, 1, 0, -1, -1, -1, 0, 1};
vector<PII> v;
map<double, char> mp;
double get_dist(const PII& v1, const PII& v2)
{
double deltax = fabs(v1.x - v2.x), deltay = (v1.y - v2.y);
return sqrt(deltax * deltax + deltay * deltay);
}
double get_hash()
{
double res = 0;
for (int i=0; i<v.size(); i++)
{
for (int j=i+1; j<v.size(); j++)
{
res += get_dist(v[i], v[j]);
}
}
return res;
}
void dfs(int x, int y)
{
g[x][y] = '0';
v.push_back({x, y});
for (int i=0; i<8; i++)
{
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < m && b >= 0 && b < n && g[a][b] == '1')
{
dfs(a, b);
}
}
}
void fill(const char& c)
{
for (int i=0; i<v.size(); i++)
{
int x = v[i].x, y = v[i].y;
g[x][y] = c;
}
}
char get_id(double sum)
{
for(auto it=mp.begin(); it!=mp.end(); it++)
{
if (fabs(it->x - sum) < 1e-6)
{
return it->y;
}
}
mp[sum] = mp.size() + 'a';
return mp[sum];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i=0; i<m; i++)
cin >> g[i];
for (int i=0; i<m; i++)
{
for (int j=0; j<n; j++)
{
if (g[i][j] == '1')
{
dfs(i, j);
double sum = get_hash();
char id = get_id(sum);
fill(id);
v.clear();
}
}
}
for (int i=0; i<m; i++)
{
for (int j=0; j<n; j++)
{
printf("%c", g[i][j]);
}
printf("\n");
}
return 0;
}
清晰! 感谢大佬
hash的部分为什么sqrt距离和用double可以过,省去sqrt用int或者long long就不过啊?
同问
+1
因为不用sqrt哈希值超longlong了,double表示数的范围大于longlong。
如果不开根号会增大有相同hash值但实际图形并不相同的情况(1连成的连通块为图形)
1 1 1 1 1
0 1
1 1 1
0 1
这两种如果都不开根号都是hash值都是20