codeforces 54B Cutting Jigsaw Puzzle題解

詳情請見：CSDN 阿史大杯茶   https://blog.csdn.net/weixin_66946161/article/details/126093709

題目意思

本題主要意思就是切成 一個個小塊（小塊的面積相同，但小塊不相同），使小塊之間互不相等，而且旋轉之後相同，也算小塊相同！例：

AB    CA
CD    DB
這兩個是相同的!

最後輸出一共可以有多少種切法，使他們互不相等，然後輸出切出的最小塊 （這裡要註意如果面積相等，則輸出 a 小的那一個）比如說： 和 ，是要輸出 !

思路：

這道題主要就是取塊以及旋轉判斷：

取塊：這個很簡單，只需雙重for迴圈，不停的枚舉中的 a 和 b，如果a或b不能被N或M整除，那麼是不行的所以要continue！

旋轉判斷：這個就比較麻煩了！首先就是旋轉，旋轉要麼是180度、90度或270度。但是長方形只用轉180度，因為長方形轉其他兩個度數會改變形狀，那麼和其他長方形就不可能相等！

180度旋轉：

A0,0 A0,1 A0,2        A2,2 A2,1 A2,0
A1,0 A1,1 A1,2        A1,2 A1,1 A1,0
A2,0 A2,1 A2,2        A0,2 A0,1 A0,0

我們可以發現Ax,y旋轉180度之後 x是從a-1->0，y是從b-1->0,所以我們就for迴圈按前面的順序讀進一個string里

for (int xx=i-1;xx>=0;xx--){//i就是a
    for (int yy=j-1;yy>=0;yy--){//j就是b
        pc+=pzl[x+xx][y+yy];
    }
}

90度旋轉：

A0,0 A0,1 A0,2        A2,0 A1,0 A0,0
A1,0 A1,1 A1,2        A2,1 A1,1 A0,1
A2,0 A2,1 A2,2        A2,2 A1,2 A0,2

我們可以發現Ax,y旋轉90度之後 x是從a-1->0，y是從0->b-1,但是我們發現每一行y沒在變化，所以y的for迴圈要在外面

for (int yy=0;yy<j;yy++){
    for (int xx=i-1;xx>=0;xx--){
        pc+=pzl[x+xx][y+yy];
    }
}

270度旋轉：

A0,0 A0,1 A0,2        A0,2 A1,2 A2,2
A1,0 A1,1 A1,2        A0,1 A1,1 A2,1
A2,0 A2,1 A2,2        A0,0 A1,0 A2,0

我們可以發現Ax,y旋轉270度之後 x是從0->a-1，y是從b-1->0,但是我們發現每一行y沒在變化，所以y的for迴圈要在外面

for (int yy=j-1;yy>=0;yy--){    
    for (int xx=0;xx<i;xx++){
        pc+=pzl[x+xx][y+yy];
    }
}

判斷是否相同：

那麼，先就來講講判斷，我們當然可以用四個圖像去判斷，但是那樣忒麻煩了！所以，我們只需每次四個旋轉圖形的最小值，所以要用string。然後放進一個set，大家知道set是可以去重的，一去重大小就不一樣了，就能很輕鬆的判斷出來了！

代碼：

#include<bits/stdc++.h>
using namespace std;
int N,M,mina,minb,ans=0;
string pc,mnpc,pzl[25];
set<string> jdg;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>N>>M;
    mina=N,minb=M;
    for (int i=0;i<N;i++) cin>>pzl[i];
    for (int i=1;i<=N;i++){
        if (N%i!=0) continue;
        for (int j=1;j<=M;j++){
            if (M%j!=0) continue;
            pc="";
            jdg.clear();
            for (int x=0;x<N;x+=i){
                for (int y=0;y<M;y+=j){
                    for (int xx=0;xx<i;xx++) for (int yy=0;yy<j;yy++) pc+=pzl[x+xx][y+yy];//賦值
                    mnpc=pc;//mnpc是四個旋轉字元串中最小的
                    pc="";
                    for (int xx=i-1;xx>=0;xx--) for (int yy=j-1;yy>=0;yy--) pc+=pzl[x+xx][y+yy];//旋轉180度
                    mnpc=min(mnpc,pc);
                    pc="";
                    if (i==j){//長方形不進行此操作
                        for (int yy=0;yy<j;yy++) for (int xx=i-1;xx>=0;xx--) pc+=pzl[x+xx][y+yy];//旋轉90度
                        mnpc=min(mnpc,pc);
                        pc="";
                        for (int yy=j-1;yy>=0;yy--) for (int xx=0;xx<i;xx++) pc+=pzl[x+xx][y+yy];//旋轉270度
                        mnpc=min(mnpc,pc);
                        pc="";
                    }
                    jdg.insert(mnpc);//set放入每一片最小值
                }
            }
            if (jdg.size()==N*M/i/j){//如果相同就會去重，因此size會不相等
                ans++;
                if ((i*j<mina*minb)||(i<mina&&i*j==mina*minb)) mina=i,minb=j;//判斷最小
            }
        }
    }
    cout<<ans<<endl;
    cout<<mina<<" "<<minb<<endl;
    return 0;
}