好吧，又是網(wǎng)格圖，題目是這樣的，在一個網(wǎng)格圖中求出聯(lián)通分量，然后判斷這個圖案之前是否出現(xiàn)過（包括旋轉(zhuǎn)、鏡像變換）
求連通分量我就不說了，簡單的DFS，然后變換的時候處理方法是旋轉(zhuǎn)矩陣r=-c,c=r，對于鏡像變換只要對r或者c取反就可以。然后為了判斷方便，最后進行最小表示，即對連通分量中的點進行排序，并將第一個點的坐標平移到(0,0)
代碼如下（逐漸喜歡上java寫程序了~）
1 import java.io.*;
2 import java.util.*;
3 public class Main {
4
5 /**
6 * @param args
7 */
8 static class point implements Comparable<point>
9 {
10 int r,c;
11 public int compareTo(point pos)
12 {
13 if(r!=pos.r) return r-pos.r;
14 else return c-pos.c;
15 }
16 public point(int rr,int cc)
17 {
18 r=rr;
19 c=cc;
20 }
21 }
22 static class block
23 {
24 int num=0;
25 char sym=0;
26 ArrayList<point> data=new ArrayList<point>();
27 ArrayList<point> ori=new ArrayList<point>();
28 public void sort()
29 {
30 Collections.sort(data);
31 int addr=data.get(0).r,addc=data.get(0).c;
32 for(point p:data)
33 {
34 p.c-=addc;
35 p.r-=addr;
36 }
37 }
38 public boolean equals(block pos)
39 {
40 if(num!=pos.num) return false;
41 for(int i=0;i<data.size();i++)
42 if(data.get(i).r!=pos.data.get(i).r||data.get(i).c!=pos.data.get(i).c)
43 return false;
44 return true;
45 }
46 public void rotate()
47 {
48 int tr,tc;
49 for(point p:data)
50 {
51 tr=p.r;
52 tc=p.c;
53 p.r=-tc;
54 p.c=tr;
55 }
56 sort();
57 }
58 public void mirror()
59 {
60 for(point p:data)
61 p.r=-p.r;
62 sort();
63 }
64
65 }
66 static ArrayList<block> refer=new ArrayList<block>();
67 static int w,h;
68 static char map[][]=new char[101][101];
69 static block now;
70 static void dfs(int r,int c)
71 {
72 if(r>=h||r<0||c>=w||c<0||map[r][c]!='1') return;
73 map[r][c]='0';
74 now.num++;
75 now.data.add(new point(r,c));
76 now.ori.add(new point(r,c));
77 dfs(r+1,c);
78 dfs(r-1,c);
79 dfs(r,c+1);
80 dfs(r,c-1);
81 dfs(r+1,c+1);
82 dfs(r-1,c-1);
83 dfs(r+1,c-1);
84 dfs(r-1,c+1);
85 }
86 public static void main(String[] args) throws IOException{
87 BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
88 w=Integer.parseInt(in.readLine());
89 h=Integer.parseInt(in.readLine());
90 for(int i=0;i<h;i++)
91 map[i]=in.readLine().toCharArray();
92 char num='a';
93 for(int i=0;i<h;i++)
94 for(int j=0;j<w;j++)
95 if(map[i][j]=='1')
96 {
97 boolean flag=false;
98 now=new block();
99 dfs(i,j);
100 now.sort();
101 for(int k=0;k<4;k++)
102 {
103 for(block p:refer)
104 {
105 if(p.equals(now))
106 {
107 flag=true;
108 now.sym=p.sym;
109 break;
110 }
111 }
112 now.rotate();
113 }
114 if(!flag)
115 {
116 now.mirror();
117 for(int k=0;k<4&&!flag;k++)
118 {
119 for(block p:refer)
120 {
121 if(p.equals(now))
122 {
123 flag=true;
124 now.sym=p.sym;
125 break;
126 }
127 }
128 now.rotate();
129 }
130 }
131 if(!flag)
132 {
133 now.sym=num++;
134 refer.add(now);
135 }
136 for(point p:now.ori)
137 map[p.r][p.c]=now.sym;
138 }
139 for(int i=0;i<h;i++)
140 {
141 for(int j=0;j<w;j++)
142 System.out.print(map[i][j]);
143 System.out.println();
144 }
145 }
146
147 }
148