博客

codeforces 54B Cutting Jigsaw Puzzle题解

  • Post category:C++

详情请见：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;
}

 

 

原文链接：https://www.cnblogs.com/xiaowuyi/p/16542447.html

Tags: