题目链接：https://vjudge.net/problem/UVALive-7747
题意：给定r*w的图，包含若干窗户，每个窗户由“.”或“+”组成，每个窗户大小相等（矩形非正方形），相邻窗户间有“#”间隔开，大矩形的外围也是一圈“#”，求一共有多少种不同的窗户。若一个窗户经过旋转0 90 180 270或360度能与另一个窗户完全重合，则认为这两个窗户是同一种窗户。
思路：我是直接模拟的，先确定窗户的长宽，然后在大矩形中分离出每个窗户，三个get_window函数将其旋转90 180 270度得到它的三种形态，每种窗户储存在set<string>ans中，每个窗户用字符串储存，每次判断该字符串是否在ans中已存在，若该窗户四种形态均不存在，则计数加一，将加入ans中。写的很长，但是很简单明了，缺点也是太长写起来费时间，在场上出的不算太快。
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #include<cstdlib> #include<sstream> #include<deque> #include<stack> #include<set> #include<map> using namespace std; typedef long long ll; typedef unsigned long long ull; const double eps = 1e-9; const int maxn = 111 + 20; const int maxt = 300 + 10; const int mod = 10; const int dx[] = {1, -1, 0, 0}; const int dy[] = {0, 0, -1, 1}; const int Dis[] = {-1, 1, -5, 5}; const double inf = 0x3f3f3f3f; const int MOD = 1000; const double PI = acos(-1.0); int n, m, k; char g[maxn][maxn];//储存输入的原矩形 set<string> windows;//储存每种窗户 char window[maxn][maxn], window2[maxn][maxn], window3[maxn][maxn], window4[maxn][maxn];//每个窗户的四种形态 int len, wid; int ansnum; string add(){//将窗户转化成字符串形式便于储存 string ans = ""; for(int i = 0; i < len; ++i){ for(int j = 0; j < wid; ++j){ ans += window[i][j]; } } return ans; } string add2(){ string ans = ""; for(int i = 0; i < wid; ++i){ for(int j = 0; j < len; ++j){ ans += window2[i][j]; } } return ans; } string add3(){ string ans = ""; for(int i = 0; i < len; ++i){ for(int j = 0; j < wid; ++j){ ans += window3[i][j]; } } return ans; } string add4(){ string ans = ""; for(int i = 0; i < wid; ++i){ for(int j = 0; j < len; ++j){ ans += window4[i][j]; } } return ans; } void get_window2(){//将原窗户旋转90度 memset(window2, 0, sizeof window2); for(int i = 0; i < wid; ++i){ for(int j = 0; j < len; ++j){ window2[i][j] = window[len - j - 1][i]; } } } void get_window3(){//旋转180度 memset(window3, 0, sizeof window3); for(int i = 0; i < len; ++i){ for(int j = 0; j < wid; ++j){ window3[i][j] = window2[wid - j - 1][i]; } } } void get_window4(){//旋转270度 memset(window4, 0, sizeof window4); for(int i = 0; i < wid; ++i){ for(int j = 0; j < len; ++j){ window4[i][j] = window3[len - j - 1][i]; } } } void judge(){ if(windows.empty()){//碰到的第一个窗户直接加入windows中，其他的都要进行判断了 windows.insert(add()); ++ansnum; return; } string ans1 = add(); if(windows.find(ans1) != windows.end()){//出现过window return; } get_window2();//得到旋转90度后的窗户 string ans2 = add2();//转化成字符串形式便于判断和储存 if(windows.find(ans2) != windows.end()){//出现过window2 return; } get_window3(); string ans3 = add3(); if(windows.find(ans3) != windows.end()){//出现过window3 return; } get_window4(); string ans4 = add4(); if(windows.find(ans4) != windows.end()){//出现过window4 return; } windows.insert(ans1);//四种都没出现过，将其添加到windows中，种类加一 ++ansnum; } int main(){ string s; while(~scanf("%d%d", &n, &m)){ ansnum = 0; windows.clear(); memset(g, 0, sizeof g); for(int i = 0; i < n; ++i){ scanf("%s", g[i]); } len = 0, wid = 0; for(int i = 1; i < n; ++i){ if(g[i][1] != '#') ++len;//每个窗户的长 else break; } for(int j = 1; j < m; ++j){ if(g[1][j] != '#') ++wid;//每个窗户的宽 else break; } memset(window, 0, sizeof window); int x = 1, y = 1, mx = n - len - 1, my = m - wid - 1; int xx, yy; for(x = 1; x < n; x += len + 1){//遍历每一个窗户 for(y = 1; y < m; y += wid + 1){ memset(window, 0, sizeof window); xx = x + len; yy = y + wid; for(int i = x; i < xx; ++i){//将每个窗户从原矩形中分离出来 for(int j = y; j < yy; ++j){ window[i - x][j - y] = g[i][j]; } } judge();//判断是否是新出现的种类 } } printf("%d\n", ansnum);//输出窗户种类数 } return 0; }