绝对，非常考耐心，细心的一道题目，这道题目充分的说明我是考虑问题不全面的人
所以现在看来TopCoder的测试数据还都算是比较弱的，真的没有极其变态的，而且TopCoder的题目其实没有超级复杂的，或许是因为我从来没做过第三题吧。
回正题。
这道题目其实一看就知道怎么做，但是就一个字烦
首先你要用FloodFill把所有的Cluster标注出来，这个不难，而且速度很快，时间差不多也就线性的。因为你只需要遍历一遍就可以了。
问题就出在判别一个Cluster的图案以前是否出现过。
首先一个Pattern可以有8种不同的样子，这里我们就不考虑对称的那些特殊情况了，就按一般情况考虑，默认这8种都不相同。
然后你需要把除了已知的一种的剩下七种全部弄出来，其实也不需要全部，不过最差情况你肯定要全弄出来，这种情况发生在出现新的图案的时候。
然后呢，你就跟这些图案去比较，看看是不是相同，这又是一个问题，关键问题，怎么判断是不是一样！
我刚开始的做法就是，记录一个图案的左上角和右下角，也就是minx，miny，maxy，maxy
当我用FloodFill找到了一个新的Cluster的时候，我会在搜索的过程中记录当前这个图案的左上角和右下角
然后就是和已知的每个图案去比较
比较的时候，我把当前的Cluster通过变换生产不同的变种，然后去跟已知的每个图案比较。
我的问题就出在这里了，因为我是用四个角标记一个图案的，那么，很有可能，这个矩形的范围内包括不属于这个图案的点。
例如
0010
1010
0111
1111
很明显，大的那个图案的矩形框左上角是（0，0），右下角是（3，3）
这就把那个不属于他的1包含进去了。
于是，在将两个矩形进行比较的时候，必须要处理这种“噪声”元素。
按照我的这种图案记录方式，我无论怎么判断，似乎都是不行的
于是我只能改策略了，用一个Shape类来记录每一个一致的图案，注意，是精确的记录，不包含那些杂点。
而且只记录第一次出现的，因为在后面陆陆续续出现的图案中，有可能两个一样的图案的矩形框有重叠。
例如
000100000
000100000
000100000
111111100
000101000
000101000
000001000
001111111
000001000
000001000
我们可以看到，这两个“十字架”的矩形框是有重叠的。
我只是精确的记录第一次出现的图案
然后，每次用两个“纯净”的图去比较，也就是说
一是我刚刚FloodFill出来的Cluster，我会用‘2’去标记，注意是字符2
另外一个就是我一致的Shape
这样我就只需要比较他们两个图有标注的地方，如果这些地方有不一致，那么显然不是same的
其实就这么简单的事情，如果写成为代码，我估计5行都用不了。
但是我却写了200多行。
为了能节省时间，旋转90，180，270我是分别写的
1 import java.io.*;
2 /*
3 ID: yanglei4
4 LANG: JAVA
5 TASK:starry
6 */
7 public class starry{
8 public class shape {
9 public int minx,miny,maxx,maxy;
10 public int[][] pattern;
11 shape(int a,int b, int c, int d) {
12 minx = a;
13 miny = b;
14 maxx = c;
15 maxy = d;
16 pattern = new int[maxx- minx + 1][maxy - miny + 1];
17 }
18
19 public int getHeight() {
20 return maxx - minx + 1;
21 }
22
23 public int getWidth() {
24 return maxy - miny + 1;
25 }
26 }
27 shape[] shapes = new shape[126];
28
29 boolean[][] visited;
30 int[][] sky;
31 int H,W;
32 char assignedChar = 'a';
33 int minx,miny,maxx,maxy;
34
35 int count = 0;
36 PrintWriter out;
37 public void floodFill(int x, int y) {
38 visited[x][y] = true;
39 sky[x][y] = '2';
40 if (x - 1 >= 0) {
41 if (visited[x - 1][y] == false && sky[x - 1][y] == 1) {
42 if (x - 1 < minx)
43 minx = x - 1;
44 floodFill(x - 1, y);
45 }
46 if (y - 1 >= 0)
47 if (visited[x - 1][y - 1] == false && sky[x - 1][y - 1] == 1) {
48 if (x - 1 < minx)
49 minx = x - 1;
50 if (y - 1 < miny)
51 miny = y - 1;
52 floodFill(x - 1, y - 1);
53 }
54 if (y + 1 < W)
55 if (visited[x - 1][y + 1] == false && sky[x - 1][y + 1] == 1) {
56 if (x - 1 < minx)
57 minx = x - 1;
58 if (y + 1 > maxy)
59 maxy = y + 1;
60 floodFill(x - 1, y + 1);
61 }
62 }
63 if (y - 1 >= 0)
64 if (visited[x][y - 1] == false && sky[x][y - 1] == 1) {
65 if (y - 1 < miny)
66 miny = y - 1;
67 floodFill(x, y - 1);
68 }
69 if (y + 1 < W)
70 if (visited[x][y + 1] == false && sky[x][y + 1] == 1) {
71 if (y + 1 > maxy)
72 maxy = y + 1;
73 floodFill(x, y + 1);
74 }
75
76 if (x + 1 < H) {
77 if (visited[x + 1][y] == false && sky[x + 1][y] == 1) {
78 if (x + 1 > maxx)
79 maxx = x + 1;
80 floodFill(x + 1, y);
81 }
82 if (y - 1>= 0)
83 if (visited[x + 1][y - 1] == false && sky[x + 1][y - 1] == 1) {
84 if (x + 1 > maxx)
85 maxx = x + 1;
86 if (y - 1 < miny)
87 miny = y - 1;
88 floodFill(x + 1, y - 1);
89 }
90 if (y + 1 < W)
91 if (visited[x + 1][y + 1] == false && sky[x + 1][y + 1] == 1) {
92 if (x + 1 > maxx)
93 maxx = x + 1;
94 if (y + 1 > maxy)
95 maxy = y + 1;
96 floodFill(x + 1, y + 1);
97 }
98 }
99 }
100
101 public int[][] R90(int[][] source, int height, int width) {
102 int[][] result = new int[width][height];
103
104 for (int i = 0; i < height; i++)
105 for (int j = 0; j < width; j++)
106 result[j][height - i - 1] = source[i][j];
107
108 return result;
109 }
110
111 public int[][] R180(int[][] source, int height, int width) {
112 int[][] result = new int[height][width];
113
114 for (int i = 0; i < height; i++)
115 for (int j = 0; j < width; j++)
116 result[height - i - 1][width - j - 1] = source[i][j];
117
118 return result;
119 }
120
121 public int[][] L90(int[][] source, int height, int width) {
122 int[][] result = new int[width][height];
123
124 for (int i = 0; i < height; i++)
125 for (int j = 0; j < width; j++)
126 result[width - j - 1][i] = source[i][j];
127
128 return result;
129 }
130
131 public int[][] Flip(int[][] source, int height, int width) {
132 int[][] result = new int[height][width];
133
134 for (int i = 0; i < height; i++)
135 for (int j = 0; j < width; j++)
136 result[i][j] = source[i][width - j - 1];
137 return result;
138 }
139
140 public boolean isSame(int[][] source, int[][] dest, int height, int width, int pattern) {
141 for (int i = 0; i < height; i++)
142 for (int j = 0; j < width; j++) {
143 if ((dest[i][j] == pattern + 1 && source[i][j] != '2') || (dest[i][j] != pattern + 1 && source[i][j] == '2')) return false;
144 }
145 return true;
146 }
147
148 public int checkSame() {
149
150 int height = maxx - minx + 1;
151 int width = maxy - miny + 1;
152
153 int[][] dest = new int[height][width];
154
155 for (int i = minx; i <= maxx; i++)
156 for (int j = miny; j <= maxy; j++)
157 if (sky[i][j] == '2')
158 dest[i - minx][j - miny] = sky[i][j];
159
160
161 boolean same = false;
162 int i = 0;
163 for (i = 0; i < count; i++) {
164 //copy the shape
165 int[][] source = new int[shapes[i].getHeight()][shapes[i].getWidth()];
166 for (int a = 0; a < shapes[i].getHeight(); a++)
167 for (int b = 0; b < shapes[i].getWidth(); b++)
168 source[a][b] = shapes[i].pattern[a][b];
169
170 if(shapes[i].getHeight() == height && shapes[i].getWidth() == width) {
171 if (isSame(dest,source,height,width,i) == true ||
172 isSame(Flip(dest, height, width),source,height,width,i) == true ||
173 isSame(R180(dest,height,width),source, height,width,i) == true ||
174 isSame( Flip(R180(dest,height,width), height, width),source, height,width,i) == true) {
175 same = true;
176 break;
177 }
178
179 }
180 if (shapes[i].getWidth() == height && shapes[i].getHeight() == width) {
181 if (isSame(R90(dest,height,width), source, width, height,i) == true ||
182 isSame(L90(dest,height,width), source, width, height,i) == true ||
183 isSame(Flip(R90(dest,height,width), width, height), source, width,height,i) == true ||
184 isSame(Flip(L90(dest,height,width), width, height), source, width,height,i) == true) {
185 same = true;
186 break;
187 }
188 }
189 }
190
191 if (!same)
192 {
193 shapes[count] = new shape(minx,miny,maxx,maxy);
194 for (int a = 0; a < height; a++)
195 for (int b = 0; b < width; b++)
196 if (dest[a][b] == '2')
197 shapes[i].pattern[a][b] = count + 1;
198 count++;
199 return 0;
200 }
201 else
202 return i + 1;
203 }
204 public void done() throws IOException {
205 BufferedReader f = new BufferedReader(new FileReader("starry.in"));
206 out = new PrintWriter(new BufferedWriter(new FileWriter("starry.out")));
207 W = Integer.parseInt(f.readLine());
208 H = Integer.parseInt(f.readLine());
209
210 sky = new int[H][W];
211 visited = new boolean[H][W];
212
213 for (int i = 0; i < H; i++) {
214 String temp = f.readLine();
215 int len = temp.length();
216 for (int j = 0; j < len; j++)
217 sky[i][j] = temp.charAt(j) - '0';
218 }
219 for (int i = 0; i < H; i++)
220 for (int j = 0; j < W; j++)
221 if (visited[i][j] == false && sky[i][j] == 1) {
222 minx = maxx = i;
223 miny = maxy = j;
224 floodFill(i,j);
225 //System.out.println("[" + minx + "," + miny + "][" + maxx + "," + maxy + "]");
226 int temp = checkSame();
227 if (temp == 0)
228 temp = count;
229 for (int a = minx; a <= maxx; a++)
230 for (int b = miny; b <= maxy; b++)
231 if (sky[a][b] == '2') sky[a][b] = temp;
232 }
233 print();
234 out.close();
235 }
236
237 public void print() {
238 for (int i = 0; i < H; i++) {
239 for (int j = 0; j < W; j++)
240 if (sky[i][j] != 0)
241 out.print((char)(sky[i][j] + 'a' - 1));
242 else
243 out.print("0");
244 out.println();
245 }
246 }
247 public static void main(String[] args) throws IOException {
248 starry t = new starry();
249 t.done();
250 System.exit(0);
251 }
252 }