题解 P2749 【[USACO5.1]夜空繁星Starry Night】

「QQ红包」 · 2017-07-05 21:19:54 · 题解

求联通块部分同，dfs扫

然后看是不是相似用了一种很神奇的方式：求两两之间的距离，然后加起来。

然后可以AC了

/*
ID: ylx14271
PROG: starry 
LANG: C++     
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m;
int a[510][110];
char f[510][110];

int x4[510][110],y4[510][110];
double s[510];//距离和 
char c[510];
int n1,n2;

int t[510];
char ch;
double d(int x2,int y2,int x3,int y3)
{
    return sqrt((x2-x3)*(x2-x3)+(y2-y3)*(y2-y3));
}
int check(int h)//求距离
{
    for (int i1=1;i1<=n2;i1++)
        for (int j1=1;j1<=n2;j1++)
        s[h]+=d(x4[n1][i1],y4[n1][i1],x4[n1][j1],y4[n1][j1]);
    for (int ii=1;ii<n1;ii++)//是否存在相同的图形
        if (fabs(s[h]-s[ii])<=0.00001) return ii;
    return 0;
}
void dfs(int x,int y)//dfs标联通块
{
    int xx,yy;
    for (int i1=-1;i1<=1;i1++)
        for (int j1=-1;j1<=1;j1++)
        {
            if (i1==0&&j1==0) continue;
            xx=x+i1;yy=y+j1;
            if (xx<=0||yy<=0||xx>n||yy>m||a[xx][yy]==0||f[xx][yy]!='0') continue;
            f[xx][yy]=ch;.//标记
            n2++;
            x4[n1][n2]=xx;//把联通块n1的所有点都存起来算距离
            y4[n1][n2]=yy;
            dfs(xx,yy);
        }
    return;
}
int main()
{
    scanf("%d%d",&m,&n);
    for (int i=1;i<=n;i++)//读入 
        for (int j=1;j<=m;j++)
        {
            ch=getchar();
            while (ch!='0'&&ch!='1') ch=getchar();
            if (ch=='0') a[i][j]=0; else a[i][j]=1;
        }
    ch='a'-1;
    memset(f,'0',sizeof(f));
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        if (f[i][j]=='0'&&a[i][j]==1) 
        {
            n2=1,n1++;
            x4[n1][n2]=i,y4[n1][n2]=j;//标记起来求距离 
            ch++;
            c[n1]=ch;
            f[i][j]=ch,dfs(i,j);
            int flag=0;
            flag=check(n1); 
            if (flag!=0)//存在相同的联通块
            {
                ch--;
                for (int i1=1;i1<=n2;i1++) f[x4[n1][i1]][y4[n1][i1]]=c[flag];//一个一个点的改标记
            } 
        }
    //for (int i=1;i<=n1;i++) printf("%.4f ",s[i]); 
    //cout<<endl;
    for (int i=1;i<=n;i++)//输出
    {
        for (int j=1;j<=m;j++) printf("%c",f[i][j]);
        printf("\n");
    }
    return 0;
}