CF54B Cutting Jigsaw Puzzle题解

2023-11-21 08:40

本文主要是介绍CF54B Cutting Jigsaw Puzzle题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 蒟蒻来讲题,还望大家喜。若哪有问题,大家尽可提!

Hello 大家好!本蒟蒻小学生来发题解啦,快来看看今天的题目!

=========================================================================

目录

题目描述

B. Cutting Jigsaw Puzzle

Input

Output

难度

题目意思

思路:

180度旋转:

 90度旋转:

270度旋转:

判断是否相同:

代码


题目描述


B. Cutting Jigsaw Puzzle

The Hedgehog recently remembered one of his favorite childhood activities, — solving puzzles, and got into it with new vigor. He would sit day in, day out with his friend buried into thousands of tiny pieces of the picture, looking for the required items one by one.

Soon the Hedgehog came up with a brilliant idea: instead of buying ready-made puzzles, one can take his own large piece of paper with some picture and cut it into many small rectangular pieces, then mix them and solve the resulting puzzle, trying to piece together the picture. The resulting task is even more challenging than the classic puzzle: now all the fragments have the same rectangular shape, and one can assemble the puzzle only relying on the picture drawn on the pieces.

All puzzle pieces turn out to be of the same size X × Y, because the picture is cut first by horizontal cuts with the pitch of X, then with vertical cuts with the pitch of Y. If we denote the initial size of the picture as A × B, then A must be divisible by X and B must be divisible by Y (X and Y are integer numbers).

However, not every such cutting of the picture will result in a good puzzle. The Hedgehog finds a puzzle good if no two pieces in it are the same (It is allowed to rotate the pieces when comparing them, but it is forbidden to turn them over).

Your task is to count for a given picture the number of good puzzles that you can make from it, and also to find the puzzle with the minimal piece size.

Input

The first line contains two numbers A and B which are the sizes of the picture. They are positive integers not exceeding 20.

Then follow A lines containing B symbols each, describing the actual picture. The lines only contain uppercase English letters.

Output

In the first line print the number of possible good puzzles (in other words, the number of pairs (X, Y) such that the puzzle with the corresponding element sizes will be good). This number should always be positive, because the whole picture is a good puzzle itself.

In the second line print two numbers — the sizes X and Y of the smallest possible element among all good puzzles. The comparison is made firstly by the area XY of one element and secondly — by the length X.

难度:

题目意思


本题主要意思就是切成 一个个小块(小块的面积不变),使小块之间互不相等,而且旋转之后相同,也算相同!例:

AB    CA
CD    DB
这两个是相同的!

最后输出一共可以有多少种切法,使他们互不相等,然后输出切出的最小块 a\times b (这里要注意如果面积相等,则输出 a 小的那一个)比如说:1\times 2 和 2\times1,是要输出 1\times2 !

思路:


这道题主要就是取块以及旋转判断

取块:这个很简单,只需双重for循环,不停的枚举a\times b中的 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就是afor (int yy=j-1;yy>=0;yy--){//j就是bpc+=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;
}

今天的题解就到这里了!大家喜欢的点个赞,谢谢!

这篇关于CF54B Cutting Jigsaw Puzzle题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/401174

相关文章

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

C - Word Ladder题解

C - Word Ladder 题解 解题思路: 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数(也就是需要变换多少次) 开始替换时: tips: 字符串下标以0开始 我们定义两个变量a和b,用于记录当前遍历到的字符 首先是判断:如果这时a已经==b了,那么就跳过,不用管; 如果a大于b的话:那么我们就让s中的第i项替换成b,接着就直接输出S就行了。 这样

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题,笔试真题 会在第一时间跟新 🍄 题面描述等均已改编,如果和你笔试题看到的题面描述

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析

牛客小白月赛100部分题解

比赛地址:牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>

P2858 [USACO06FEB] Treats for the Cows G/S 题解

P2858 题意 给一个数组。每天把最左或者最右的东西卖掉,第 i i i个东西,第 d a y day day天卖出的价格是 a [ i ] ∗ d a y a[i]*day a[i]∗day。 记忆化搜索 void dfs(int l,int r,int day,ll sum){if(v[l][r]>=sum)return;v[l][r]=sum;if(l>r)//这就是dp答案{

【UVA】10003-Cutting Sticks(动态规划、矩阵链乘)

一道动态规划题,不过似乎可以用回溯水过去,回溯的话效率很烂的。 13988658 10003 Cutting Sticks Accepted C++ 1.882 2014-08-04 09:26:49 AC代码: #include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include

【C++题解】1272. 郭远摘苹果

欢迎关注本专栏《C++从零基础到信奥赛入门级(CSP-J)》 问题:1272. 郭远摘苹果 类型:二维数组 题目描述: 郭远有一天走到了一片苹果林,里面每颗树上都结有不同数目的苹果,郭远身上只能拿同一棵树上的苹果,他每到一棵果树前都会把自己身上的苹果扔掉并摘下他所在树上的苹果并带走(假设郭远会走过每一棵苹果树),问在郭远摘苹果的整个过程中,他身上携带的最多苹果数与最小苹果数的差是多少?

【最新华为OD机试E卷-支持在线评测】机器人活动区域(100分)多语言题解-(Python/C/JavaScript/Java/Cpp)

🍭 大家好这里是春秋招笔试突围 ,一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-E/D卷的三语言AC题解 💻 ACM金牌🏅️团队| 多次AK大厂笔试 | 编程一对一辅导 👏 感谢大家的订阅➕ 和 喜欢💗 🍿 最新华为OD机试D卷目录,全、新、准,题目覆盖率达 95% 以上,支持题目在线评测,专栏文章质量平均 94 分 最新华为OD机试目录: https://blog.