Codeforces 54 B. Cutting Jigsaw Puzzle

問題

XxYの文字列で与えられる長方形の紙がある。
これをAxBの長方形に切る(AはXの約数かつBはYの約数でなければならない)
切ったあとの長方形について、かかれている文字が同一であるものがあってはならない。
(回転して重なるものは同一とみなす。左右反転は不可)


このとき、A,Bの値としてありうるものは何通りか出力し、
A*Bが最小をとるときのA,Bの値(複数ある場合Aが最小のもの)を出力せよ。

制約条件

X,Y≦20

方針

全列挙。

ソースコード

int n,m;
bool contain(set<vs> &s,vs v){
  rep(d,4){
    if(s.count(v))return 1;
    vs nxt(v[0].size(),string(v.size(),' '));
    rep(i,v[0].size())rep(j,v.size())nxt[i][j]=v[v.size()-j-1][i];
    v=nxt;
  }
  return 0;
}
void run(){
  cin>>n>>m;
  int x=n,y=m,cnt=0;
  vs in(n);
  rep(i,n)cin>>in[i];
  for(int a=1;a<=n;a++)for(int b=1;b<=m;b++){
    if(n%a||m%b)continue;
    set<vs> s;
    rep(i,n/a)rep(j,m/b){
      vs v(a);
      rep(k,a)rep(l,b)v[k].pb(in[a*i+k][b*j+l]);
      if(contain(s,v))goto FAIL;
      s.insert(v);
    }
    cnt++;
    if(x*y>a*b||x*y==a*b&&x>a)x=a, y=b;
    FAIL:;
  }
  cout<<cnt<<endl;
  cout<<x<<" "<<y<<endl;
}