【-88】 P2749 [USACO5.1]夜空繁星Starry Night[dfs]

题目背景

高高的星空,簇簇闪耀的群星形态万千。一个星座(cluster)是一群连通的星组成的非空连通星系,这里的连通是指水平,垂直或者对角相邻的两个星星。一个星座不能是另一个更大星座的一部分, 星座可以相似(similar)。如果两个星座有相同的形状,而且包括相同数目的星体,那么不管其方向性如何,就算相似。一般而言,星座可能的方向有八个,如图1所示。

题目描述

夜空可以表示为一份天体图(sky map),它是一个由字符0和1组成的二维矩阵,字符1表示所在的位置有一颗星;字符0表示该位置上是空的.给定一份天体图,用同一个小写英文标识(mark)相似的所有星座。相似的星座必须用相同的字母标识,不同的星座表示为不同的字母。标识一个星座,就是将其中各星体对应的字符1替换为相应的小写字母.

输入输出格式

输入格式:

文件的前两行分别记录了天体图的宽度W、深度H。而天体图则是由接下来的H行表示,每行包括W个字符. ……

输出格式:

输出文件记录了天体图与文件STARRY.IN相似,不同之处在于,各个星座按照“任务”中的要求进行了标识(mark)。

对于同一个输入文件,可能会有很多不同的标识,此时,输出字典序最小的标识。

输入输出样例

输入样例#1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
23
15
10001000000000010000000
01111100011111000101101
01000000010001000111111
00000000010101000101111
00000111010001000000000
00001001011111000000000
10000001000000000000000
00101000000111110010000
00001000000100010011111
00000001110101010100010
00000100110100010000000
00010001110111110000000
00100001110000000100000
00001000100001000100101
00000001110001000111000

输出样例#1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
a000a0000000000b0000000
0aaaaa000ccccc000d0dd0d
0a0000000c000c000dddddd
000000000c0b0c000d0dddd
00000eee0c000c000000000
0000e00e0ccccc000000000
b000000e000000000000000
00b0f000000ccccc00a0000
0000f000000c000c00aaaaa
0000000ddd0c0b0c0a000a0
00000b00dd0c000c0000000
000g000ddd0ccccc0000000
00g0000ddd0000000e00000
0000b000d0000f000e00e0b
0000000ddd000f000eee000

说明

在这种情况下,天体图是一个长23宽为15的二维矩阵。请注意这幅天体图是对应(corresponds to)下面这个矩阵的图像。

Starry-2.gif 图starry-2:天体图

这是上述输入实例的一个可能的结果。请注意,该输出文件对应于下面的天空景象。

题解

求联通块部分同,dfs扫
然后看是不是相似用了一种很神奇的方式:求两两之间的距离,然后加起来。
然后可以AC了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/*
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<=n;i++)//输出
{
for (int j=1;j<=m;j++) printf("%c",f[i][j]);
printf("\n");
}
return 0;
}