这个题就是图像识别类型的模拟题， 我们可以先将每个图像所在的矩形求出来然后在进行比对，实现的时候我们对每个图形进行染色， 记录染色的区域， 在统计一下染色的数目， 那个两个图像相同的充分必要条件就是a的数目等于b的数目，a染色的区域b也染色。代码如下：
/* ID: m1500293 LANG: C++ PROG: starry */ #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; int H, W; char Map[110][110]; struct Mat { int x1, y1, x2, y2; int num; //联通块的数量 }mat[550]; int nmat; void update(int x, int y) { if(!mat[nmat].x1 || mat[nmat].x1>x) mat[nmat].x1 = x; if(!mat[nmat].y1 || mat[nmat].y1>y) mat[nmat].y1 = y; if(!mat[nmat].x2 || mat[nmat].x2<x) mat[nmat].x2 = x; if(!mat[nmat].y2 || mat[nmat].y2<y) mat[nmat].y2 = y; } //bool vis[110][110]; int col[110][110]; struct P{ int x, y; }; bool inside(int x, int y) { return (x>=1&&x<=H&&y>=1&&y<=W); } int flood(int x, int y, int co) { int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1}; int dy[] = {0, -1, 0, 1, 1, -1, -1, 1}; int num = 1; //vis[x][y] = 1; col[x][y] = co; update(x, y); queue<P> que; que.push((P){x, y}); while(!que.empty()) { P u = que.front(); que.pop(); for(int i=0; i<8; i++) { int nx = u.x+dx[i], ny = u.y + dy[i]; if(inside(nx, ny) && col[nx][ny]==-1 && Map[nx][ny]=='1') { que.push((P){nx, ny}); num++; update(nx, ny); col[nx][ny] = co; } } } return num; } char res[110][110], p[550]; void rot(char a[][110], int lx, int ly) //顺时针旋转90 { char tp[110][110]; for(int i=0; i<lx; i++) for(int j=0; j<ly; j++) tp[j][lx-i-1] = a[i][j]; for(int i=0; i<ly; i++) for(int j=0; j<lx; j++) a[i][j] = tp[i][j]; } void turn(char a[][110], int lx, int ly) { for(int i=0; i<lx; i++) for(int j=0; j<ly/2; j++) swap(a[i][j], a[i][ly-1-j]); } bool ok(int aa, char a[][110], int lx, int ly) { for(int i=0; i<lx; i++) for(int j=0; j<ly; j++) { int ox = mat[aa].x1+i, oy = mat[aa].y1+j; if(col[ox][oy]==aa && a[i][j]=='0') return false; } return true; } bool same(int a, int b) { if(mat[a].num != mat[b].num) return false; char temp[110][110]; int ax = mat[a].x2-mat[a].x1+1, ay = mat[a].y2-mat[a].y1+1; int lx = mat[b].x2-mat[b].x1+1, ly = mat[b].y2-mat[b].y1+1; for(int i=0; i<lx; i++) for(int j=0; j<ly; j++) { int ox = i+mat[b].x1, oy = j+mat[b].y1; temp[i][j] = Map[ox][oy]; } if(ax==lx && ay==ly && ok(a, temp, lx, ly)) return true; for(int i=0; i<4; i++) { rot(temp, lx, ly); swap(lx, ly); if(ax==lx && ay==ly && ok(a, temp, lx, ly)) return true; } turn(temp, lx, ly); for(int i=0; i<4; i++) { rot(temp, lx, ly); swap(lx, ly); if(ax==lx && ay==ly && ok(a, temp, lx, ly)) return true; } return false; } int main() { freopen("starry.in", "r", stdin); freopen("starry.out", "w", stdout); scanf("%d%d", &W, &H); for(int i=1; i<=H; i++) scanf("%s", Map[i]+1); nmat = 0; memset(col, -1, sizeof(col)); for(int i=1; i<=H; i++) for(int j=1; j<=W; j++) if(Map[i][j]=='1' && col[i][j]==-1) { int n = flood(i, j, nmat); mat[nmat].num = n; nmat++; } memcpy(res, Map, sizeof(Map)); char c = 'a'; for(int i=0; i<nmat; i++) { int idx = -1; for(int j=0; j<i; j++) if(same(i, j)) { idx = j; break; } if(idx != -1) p[i] = p[idx]; else p[i] = c++; for(int ii=mat[i].x1; ii<=mat[i].x2; ii++) for(int j=mat[i].y1; j<=mat[i].y2; j++) if(col[ii][j]==i) res[ii][j] = p[i]; } for(int i=1; i<=H; i++) { for(int j=1; j<=W; j++) printf("%c", res[i][j]); printf(" "); } return 0; }