絕對，非?？寄托?，細心的一道題目，這道題目充分的說明我是考慮問題不全面的人
所以現在看來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 }