分析
利用bfs遍历所有图中的连通块,之后把找到的字符c替换连通块中所有原来的字符。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
const double eps = 1e-8;
int dx[8]={1,0,-1,0,-1,-1,1,1};
int dy[8]={0,1,0,-1,-1,1,-1,1};
int n,m,hh,tt=-1,id;
char g[N][N];
bool st[N][N];
struct point{
int x,y;
}q[N*N];
void bfs(int x,int y) //bfs搜索每一个连通块
{
point t;
t.x=x,t.y=y;
q[++tt]=t;
st[t.x][t.y]=true;
while(hh<=tt)
{
t=q[hh++];
point cur;
for(int i=0;i<8;i++) //一共有8个方向
{
cur.x=t.x+dx[i];
cur.y=t.y+dy[i];
if(cur.x>=0 && cur.x<n && cur.y>=0 && cur.y<m && g[cur.x][cur.y]=='1' && !st[cur.x][cur.y])
{
st[cur.x][cur.y]=true; //当前点遍历过
q[++tt]=cur; //当前点加入队列
}
}
}
}
double get_hash()
{
double sum=0;
for(int i=0;i<=tt;i++)
{
for(int j=i+1;j<=tt;j++)
{
double x_2=(q[i].x-q[j].x)*(q[i].x-q[j].x);
double y_2=(q[i].y-q[j].y)*(q[i].y-q[j].y);
sum+=sqrt(x_2+y_2);
}
}
return sum;
}
char getc(double val)
{
static double mp[30]; //static可认为是全局变量
for(int i=0;i<id;i++)
{
if(fabs(mp[i]-val)<eps)
{
return i+'a';
}
}
mp[id++]=val;
return id-1+'a';
}
int main()
{
ios::sync_with_stdio(false);
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')
{
tt=-1,hh=0; //每次搜索前将队列清空
bfs(i,j);
char c=getc(get_hash());
for(int k=0;k<=tt;k++) //所有入队的点的值更新为新的字符c
{
g[q[k].x][q[k].y]=c;
}
}
}
}
for(int i=0;i<n;i++) cout<<g[i]<<endl;
return 0;
}