题目链接

https://vjudge.net/problem/572937/origin

题目大意

给你一大块字符串， 里面有规则且大小相等的矩阵， 问你这些矩阵中， 不重复的有几个（矩阵可旋转不可翻转）

核心思想

把矩阵转化为一个string， 旋转后也可以得到另一个string， 如果矩阵长宽相等就有4个， 否则就两个， 最后转化为比较得到的string就行了，最多n^2 （别人都是哈希做的， 本弱鸡暂时不会哈希）

优化

将得到的4个或2个string排序取字典序最小的将得到的string放入vetcor中用unique(）函数去重

代码

#include<bits/stdc++.h> using namespace std; char s[120][120]; char w[20000][120][120]; string ss[20000][6];//第一维记录第几个矩阵， 开小了会re， 矩阵可能会很多 vector<string>cnt; int main() { int r ,c; while(~scanf("%d%d", &r, &c)) { cnt.clear(); int cc=0, rr=0, ans=0; for(int i=0; i<20000; ++i) for(int j=0; j<6; ++j) ss[i][j].clear(); for(int i=1; i<=r; ++i) scanf("%s", s[i]+1); for(int i=2; i<=c; ++i)//计算矩阵大小 { if(s[2][i] == '#') break; ++cc; } for(int i=2; i<=r; ++i) { if(s[i][2] == '#') break; ++rr; } int tot = ((r-1)/(rr+1))*((c-1)/(cc+1));//计算矩阵个数 int tt=1; for(int i=2; i<r; i+=(rr+1))//将每个矩阵存下来 { for(int j=2; j<c; j+=(cc+1)) { for(int ii= i; ii < i+rr; ++ii) { for(int jj=j; jj<j+cc; ++jj) { w[tt][ii-i+1][jj-j+1] = s[ii][jj]; } } ++tt; } } if(rr == cc) { for(int t=1; t<=tot; ++t) { string ns; ns.clear(); for(int i=1; i<=rr; ++i)//旋转 { for(int j=1; j<=cc; ++j) { ns +=w[t][i][j]; } } ss[t][0] = ns; ns.clear(); for(int i=cc; i>=1; --i) { for(int j=1; j<=rr; ++j) { ns +=w[t][j][i]; } } ss[t][1] = ns; ns.clear(); for(int i=rr; i>=1; --i) { for(int j=cc; j>=1; --j) { ns +=w[t][i][j]; } } ss[t][2] = ns; ns.clear(); for(int i=1; i<=cc; ++i) { for(int j=rr; j>=1; --j) { ns +=w[t][j][i]; } } ss[t][3] = ns; } for(int i=1; i<=tot; ++i) sort(ss[i], ss[i]+4); for(int i=1; i<=tot; ++i) cnt.push_back(ss[i][0]); sort(cnt.begin(), cnt.end());//使用unique（）前需要将vector里的元素排序 ans = unique(cnt.begin(), cnt.end()) -cnt.begin();//去重 } else { for(int t=1; t<=tot; ++t) { string ns; ns.clear(); for(int i=1; i<=rr; ++i) { for(int j=1; j<=cc; ++j) { ns +=w[t][i][j]; } } ss[t][0] = ns; ns.clear(); for(int i=rr; i>=1; --i) { for(int j=cc; j>=1; --j) { ns +=w[t][i][j]; } } ss[t][1] = ns; } for(int i=1; i<=tot; ++i) sort(ss[i], ss[i]+2); for(int i=1; i<=tot; ++i) cnt.push_back(ss[i][0]); sort(cnt.begin(), cnt.end()); ans = unique(cnt.begin(), cnt.end()) -cnt.begin(); } cout<<ans<<endl; } return 0; } //可以缩行第地方有很多