把所有的连通块，左上角，右下角的坐标当作一个矩形存起来。然后枚举，跟之前的是不是相同。
注意：连通块转化成矩阵的时候，只有一起连通的的点，在小的矩形里才为1，而不是str[i][j] =='1'，这里错了次。。写的很麻烦。。
1 /* 2 ID:cuizhe 3 LANG: C++ 4 TASK: starry 5 */ 6 #include7 #include 8 #include 9 using namespace std; 10 struct node 11 { 12 int n,m; 13 int lx,ly,rx,ry; 14 int flag; 15 } p[2001]; 16 char str[101][101]; 17 int o[101][101],w,h; 18 int t1[101][101],t2[101][101]; 19 int lx,ly,rx,ry; 20 int kk[2001]; 21 int a[8] = { 1,1,1,0,0,-1,-1,-1}; 22 int b[8] = { 0,-1,1,-1,1,0,1,-1}; 23 void CL() 24 { 25 lx = 1000000; 26 ly = 1000000; 27 rx = -1; 28 ry = -1; 29 } 30 void dfs(int x,int y,int num) 31 { 32 int i; 33 lx = min(x,lx); 34 ly = min(y,ly); 35 rx = max(rx,x); 36 ry = max(ry,y); 37 for(i = 0; i < 8; i ++) 38 { 39 if(x+a[i]>=0&&x+a[i] < h&&y+b[i] >= 0&&y+b[i] < w&&!o[x+a[i]][y+b[i]]&&str[x+a[i]][y+b[i]] == '1') 40 { 41 o[x+a[i]][y+b[i]] = num; 42 dfs(x+a[i],y+b[i],num); 43 } 44 } 45 return ; 46 } 47 int fun(int x,int y) 48 { 49 int i,j,z,n,m; 50 n = p[x].n; 51 m = p[x].m; 52 if(p[x].n == p[y].n&&p[x].m == p[y].m) 53 { 54 z = 1; 55 for(i = 0; i < n&&z; i ++) //相等 56 { 57 for(j = 0; j < m&&z; j ++) 58 { 59 if(t1[i][j] != t2[i][j]) 60 z = 0; 61 } 62 } 63 if(z) return 1; 64 z = 1; 65 for(i = 0; i < n&&z; i ++) //旋转180 66 { 67 for(j = 0; j < m&&z; j ++) 68 { 69 if(t1[i][j] != t2[n-i-1][m-j-1]) 70 z = 0; 71 } 72 } 73 if(z) return 1; 74 z = 1; 75 for(i = 0; i < n&&z; i ++) //翻转 76 { 77 for(j = 0; j < m&&z; j ++) 78 { 79 if(t1[i][j] != t2[i][m-j-1]) 80 z = 0; 81 } 82 } 83 if(z) return 1; 84 z = 1; 85 for(i = 0; i < n&&z; i ++) //翻转然后旋转180 86 { 87 for(j = 0; j < m&&z; j ++) 88 { 89 if(t1[i][j] != t2[n-i-1][j]) 90 z = 0; 91 } 92 } 93 if(z) return 1; 94 } 95 if(p[x].n == p[y].m&&p[x].m == p[y].n) 96 { 97 z = 1; 98 for(i = 0; i < n&&z; i ++) //旋转90 99 {100 for(j = 0; j < m&&z; j ++)101 {102 if(t1[i][j] != t2[j][n-i-1])103 z = 0;104 }105 }106 if(z) return 1;107 z = 1;108 for(i = 0; i < n&&z; i ++) //旋转270109 {110 for(j = 0; j < m&&z; j ++)111 {112 if(t1[i][j] != t2[m-j-1][i])113 z = 0;114 }115 }116 if(z) return 1;117 z = 1;118 for(i = 0; i < n&&z; i ++) //先翻转后旋转90119 {120 for(j = 0; j < m&&z; j ++)121 {122 if(t1[i][j] != t2[m-j-1][n-i-1])123 z = 0;124 }125 }126 if(z) return 1;127 z = 1;128 for(i = 0; i < n&&z; i ++) //先翻转后旋转270129 {130 for(j = 0; j < m&&z; j ++)131 {132 if(t1[i][j] != t2[j][i])133 z = 0;134 }135 }136 if(z) return 1;137 }138 return 0;139 }140 int judge(int x,int y)141 {142 int i,j;143 if(p[x].n == p[y].n&&p[x].m == p[y].m)144 ;145 else if(p[x].n == p[y].m&&p[x].m == p[y].n)146 ;147 else148 return 0;149 for(i = p[x].lx; i <= p[x].rx; i ++)//转化为两个01矩阵150 {151 for(j = p[x].ly; j <= p[x].ry; j ++)152 {153 if(o[i][j] == x)154 t1[i-p[x].lx][j-p[x].ly] = 1;155 else156 t1[i-p[x].lx][j-p[x].ly] = 0;157 }158 }159 for(i = p[y].lx; i <= p[y].rx; i ++)160 {161 for(j = p[y].ly; j <= p[y].ry; j ++)162 {163 if(o[i][j] == y)164 t2[i-p[y].lx][j-p[y].ly] = 1;165 else166 t2[i-p[y].lx][j-p[y].ly] = 0;167 }168 }169 170 if(fun(x,y))171 return 1;172 else173 return 0;174 }175 int main()176 {177 int i,j,num;178 freopen("starry.in","r",stdin);179 freopen("starry.out","w",stdout);180 scanf("%d%d",&w,&h);181 for(i = 0; i < h; i ++)182 {183 scanf("%s",str[i]);184 }185 num = 1;186 for(i = 0; i < h; i ++)187 {188 for(j = 0; j < w; j ++)189 {190 if(!o[i][j]&&str[i][j] == '1')191 {192 o[i][j] = num;193 CL();194 dfs(i,j,num);195 p[num].lx = lx;196 p[num].ly = ly;197 p[num].rx = rx;198 p[num].ry = ry;199 p[num].flag = 0;200 p[num].n = rx - lx + 1;201 p[num].m = ry - ly + 1;202 num ++;203 }204 }205 }206 for(i = 2; i < num; i ++)207 {208 for(j = 1; j < i; j ++)209 {210 if(p[j].flag) continue;211 if(judge(i,j))212 {213 p[i].flag = j;214 break;215 }216 }217 }218 num = 1;219 for(i = 0; i < h; i ++)220 {221 for(j = 0; j < w; j ++)222 {223 if(str[i][j] == '1')224 {225 if(p[o[i][j]].flag)226 {227 kk[o[i][j]] = kk[p[o[i][j]].flag];228 }229 else230 {231 if(!kk[o[i][j]])232 kk[o[i][j]] = num ++;233 }234 printf("%c",kk[o[i][j]]-1+'a');235 }236 else237 printf("0");238 }239 printf("\n");240 }241 return 0;242 }