北京国互网网站建设公司,东莞寮步搬家公司,asp网站做视频,创业型企业网站模板AcWing 1402. 星空之夜 1月28
题意#xff1a;
一个星群是指一组非空的在水平#xff0c;垂直或对角线方向相邻的星星的集合。 一个星群不能是一个更大星群的一部分。 星群可能是相似的。 如果两个星群的形状、包含星星的数目相同#xff0c;那么无论它们的朝向如何#…AcWing 1402. 星空之夜 1月28
题意
一个星群是指一组非空的在水平垂直或对角线方向相邻的星星的集合。 一个星群不能是一个更大星群的一部分。 星群可能是相似的。 如果两个星群的形状、包含星星的数目相同那么无论它们的朝向如何都认为它们是相似的。 给定一个夜空二维矩阵请你将其中的所有星群用小写字母进行标记标记时相似星群用同一字母不相似星群用不同字母。
题解
本题的关键在于如何判断两个星群是否相似也就是如何分配字母的问题。题目说了相似说明两个星群形状一样与方向无关形状这一特征我们可以从每个星星与其他星星的距离和来表示 对于每一个星群计算其内部距离和然后看之前是否出现过出现过则给之前的字母若没出现则根据出现顺序赋予字母
代码
代码思路肯定是对的但是不知道哪错了
#includebits/stdc.h
typedef long long ll;
using namespace std;
inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
int dy[9]{-1,0,1,-1,1,-1,0,1},dx[9]{-1,-1,-1,0,0,1,1,1};
const int maxn600;
char a[maxn][maxn];
char newa[maxn][maxn];
int w,h;
vectorpairint,int c;
vectorllmapp;
void dfs(int x,int y)
{a[x][y]0;c.push_back({x,y});for(int i0;i7;i){int txxdx[i];int tyydy[i];if(a[tx][ty]0||txh||tx0||tyw||ty0)continue;dfs(tx,ty);}
}
ll getsum()
{ll sum0;for(int i0;ic.size();i){for(int ji1;jc.size();j){sum(c[i].first-c[j].first)*(c[i].first-c[j].first)(c[i].second-c[j].second)*(c[i].second-c[j].second);}}return sum;
}
char check(ll sum)
{for(int i0;imapp.size();i){if(mapp[i]sum)return (char)(ai);}char newwamapp.size();mapp.push_back(sum);return neww;
}
void fill(char x)
{for(int i0;ic.size();i){newa[c[i].first][c[i].second]x;}
}
int main()
{memset(newa,0,sizeof(newa));cinwh;for(int i1;ih;i){for(int j1;jw;j){cina[i][j];}//char chgetchar();}for(int i1;ih;i){for(int j1;jw;j){if(a[i][j]1){dfs(i,j);ll sumgetsum();char xcheck(sum);fill(x);c.clear();}}}for(int i1;ih;i){for(int j1;jw;j){printf(%c,newa[i][j]);}printf(\n);}
}
