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; }