怎么自己给自己的网站做推广,北京网站建设定制,帮人做网站赚钱吗,宁波网站建设设计服务公司以前玩俄罗斯方块的时候#xff0c;就想过一个问题#xff0c;为什么俄罗斯方块就这7种形状#xff0c;还有没有别的形状#xff1f;自己也在纸上画过#xff0c;比划来比划去#xff0c;确实就这几种形状。
继续思考一下#xff0c;那假如是3个块组合的形状#xff0…以前玩俄罗斯方块的时候就想过一个问题为什么俄罗斯方块就这7种形状还有没有别的形状自己也在纸上画过比划来比划去确实就这几种形状。
继续思考一下那假如是3个块组合的形状有几种有效组合形式
这个似乎不是太难在纸上比划几下应该能得出结果。
但是如果是5个块组合起来又有多少种有效的组合形式
这就比较麻烦了排列组合的可能性大增不那么容易比划清楚。
从程序员的角度这其实是一个遍历穷举的过程所以有了这一篇文章。
首先也不搞太复杂的先从3个块的组合开始尝试。
3个块的组合考虑所有可能性就是在3x3的一个区域里面任意取点。然后添加一些限制条件例如
1区域内点位不重复 2每个点都至少需要有一个相邻点 3平移不重复 4旋转不重复
这4个条件是否充足了
反正我开始时就是这么想的认为充足了。当然到后面遇到了问题才又添加了个限制条件。
为了能方便的判断结果是否正确将有效结果展示出来是有必要的。
需要界面展示这里选择了是要QT毕竟有可移植性在windows下开发以后要移植到linux下也可以。
看一下基本的布局界面是这样的 左上角是那个画出方块组合形状的区域。在遍历过程中遇到有效的方块组合就在下面区域中以一半的宽高比例画出来。
这里由于涉及到了方块组合的不同大小的展示以及还有平移动作就需要考虑方块的点坐标不能存储实际的宽高值例如0,20,40而是更抽象的基础比例例如0,1,2。
下面是简要介绍实现过程具体实现可从文末的下载地址去获取。
先定义方块的类
class Block
{
public:QPoint leftUp;//左上角的坐标int width;//宽度int height;//高度QColor penColor;//铅笔的颜色QColor brushColor;//画刷的颜色
}
再定义一个方块组合的类
class BlockGroup
{
public:BlockGroup(int num);int blockNum;//方块的数目Block block[BLOCK_NUM];//方块的数组int flagValid;//有效标志
};
一个穷举遍历的主要过程如下 int pos[5];int pointTotalpow(curBlock.blockNum,2);//一个点可以选择的位置int tryNum pow(pointTotal,curBlock.blockNum);//每一个点都有这么多种可能的位置总的可能点位选择while(tickNumtryNum){//遍历所有的可能性for(int i0;icurBlock.blockNum;i){//将一个大数分解为几个部分每部分给一个方块使用用作坐标赋值int pointLevelpow(pointTotal,curBlock.blockNum-1-i);pos[i](tickNum/pointLevel)%pointTotal;}//计算寻找有效的方块组合for(int j0;jcurBlock.blockNum;j){curBlock.block[j].leftUp.setX((xpos[j]/curBlock.blockNum)*w);curBlock.block[j].leftUp.setY((ypos[j]%curBlock.blockNum)*h);curBlock.block[j].width w;curBlock.block[j].height h;curBlock.block[j].penColor Qt::black;curBlock.block[j].brushColor Qt::yellow;}if(checkPosValid(curBlock)!1){//内部有点位重复此种组合无效跳过tickNum1;continue;}if(checkAdjacent(curBlock)!1){//检测每点都有相邻点若不是跳过tickNum1;continue;}if(checkConnectivity(curBlock)!1){//检测组块内部的连通性若不是跳过tickNum1;continue;}//规范坐标adjustCoordinates(curBlock);int flagRepeat0;for(auto itblockGroupList.begin();it!blockGroupList.end();it){if(checkTranslationRepeatability((*it),curBlock)){//发现是平移重复的flagRepeat1;break;}if(checkRotaltionalRepeatability((*it),curBlock)){//发现是旋转重复的flagRepeat1;break;}}if(flagRepeat1){tickNum1;continue;}//新的有效方块组合存入结果链表中blockGroupList.push_back(curBlock);//写文件writeBlockInfo(curBlock);//设置标志通知画出 flagFlush1;update();break; }
下面逐个展示循环里面调用的方法。
检查方块组合中的点位是否重复
//检测块内点位是否有效不能重复
int BlockDialog::checkPosValid(BlockGroup *blockInfo){for(int k0;kblockInfo-blockNum-1;k){for(int ik1;iblockInfo-blockNum;i){if(blockInfo-block[k].leftUpblockInfo-block[i].leftUp){return 0;}}}return 1;
}
检查不是孤立点位
//检测两点是否相邻
int BlockDialog::checkNearPoint(QPoint *point1,QPoint *point2,int w,int h){QPoint pointRightQPoint(w,0);QPoint pointDownQPoint(0,h);if(*point1pointRight *point2){//右邻return 1;}if(*point1 *point2pointRight){//左邻return 1;}if(*point1pointDown *point2){//下邻return 1;}if(*point1 *point2pointDown){//上邻return 1;}return 0;//不相邻
}
//检测有相邻块
int BlockDialog::checkAdjacent(BlockGroup *blockInfo){int isNearNum0;for(int i0;iblockInfo-blockNum;i){isNearNum0;for(int k0;kblockInfo-blockNum;k){if(k!i){if(1checkNearPoint(blockInfo-block[k].leftUp, blockInfo-block[i].leftUp,blockInfo-block[i].width,blockInfo-block[i].height)){isNearNum;}}}if(isNearNum0){//没有相邻点return 0;}}return 1;
}
已经检查过不是孤立点了为什么还要检查点的连通性checkConnectivity
这就是前面说过的那个添加的限制条件。为什么呢
前面列举了4个限制条件在应用到3个方块组合时没有遇到问题但是在穷举4个方块的组合的时候就遇到了问题例如下面这种方块组合竟然是满足条件的 然而这并不是我期望的形状我希望所有方块都是相连通的。没有孤立方块这个条件没有包含所有方块连通的要求所以还需要增加一个限制条件
5要保证所有方块是连通起来的。
如下代码是检测方法
//检测块内连通性
int BlockDialog::checkConnectivity(BlockGroup *blockInfo){int isNearNum0;//将块组各点位信息赋值到节点中Node *nodeArraynew Node[blockInfo-blockNum];for(int i0;iblockInfo-blockNum;i){nodeArray[i].point blockInfo-block[i].leftUp;}//设置相邻节点for(int i0;iblockInfo-blockNum;i){for(int j0;jblockInfo-blockNum;j){if(i!j){setNearNode(nodeArray[i],nodeArray[j]);}}}//从节点0开始进行遍历DepthFirstSearch(nodeArray[0]);//检查是否有未遍历到的结点for(int i0;iblockInfo-blockNum;i){if(1nodeArray[i].isChecked){isNearNum;} else {break;//有未走到的点即组块有未连通部分}}delete[] nodeArray;if(isNearNumblockInfo-blockNum){//完成遍历即方块组是连通的return 1;}return 0;
}
这里调用了一个函数 DepthFirstSearch() 是深度优先搜索算法。
这里涉及到图的连通性参考这个链接讲得比较清楚 https://blog.csdn.net/weixin_44122303/article/details/122924246
//深度优先搜索--遍历相邻节点
void DepthFirstSearch(Node *node){if(nodeNULL){return;}//递归调用注意避免无限循环if(node-isChecked1){//已经检查过的不要再进行检查了避免无限循环return;}//设置检查标志node-isChecked1;//递归调用检查相邻点DepthFirstSearch(node-up);DepthFirstSearch(node-down);DepthFirstSearch(node-left);DepthFirstSearch(node-right);return ;
}
这里还有一个规范坐标的函数 adjustCoordinates(curBlock); 为什么需要它
也是在遇到问题之后才知道的。
在平移比较方块组合是否是重复的情况时发现明明是一样的形状却判断为不重复。
细细分析之后发现是顺序不同例如如下情况
0,1,2与0,2,1
都是3个直线相邻的方块但是由于顺序不同直接按逐点比较的话属于不同的组合。所以添加一个规范点位顺序的方法
//规范坐标
//1左上平移;
//2按顺序存放从左上角开始先第一排从左往右然后第二排
int BlockDialog::adjustCoordinates(BlockGroup *blockInfo){//定位左上角方块的坐标QPoint leftTopPoint1(0,0);QPoint leftTopPoint2getLeftTopBoundary(blockInfo);//1对整个方块组进行平移int leftShift leftTopPoint2.x()-leftTopPoint1.x();int upShift leftTopPoint2.y()-leftTopPoint1.y();QPoint pointShift(leftShift,upShift);Block blockTmpBlock();listBlock listBlock{};for(int i0;iblockInfo-blockNum;i){blockTmp.leftUpblockInfo-block[i].leftUp-pointShift;blockTmp.penColorblockInfo-block[i].penColor;//进行块组的赋值注意不能遗漏颜色属性blockTmp.brushColorblockInfo-block[i].brushColor;listBlock.push_back(blockTmp);}//2排序 -- 按什么顺序排列的//重载Block的比较操作符 顺序定义从左上角开始先第一排从左往右然后第二排listBlock.sort();int blockPos0;for(auto itlistBlock.begin();it!listBlock.end();it){blockInfo-block[blockPos]*it;blockPos;}return 0;
}
这里的排序方法依赖的是比较操作先比较点位的纵坐标y再比较横坐标x bool operator(const Block block1) const{if(this-leftUp.y()block1.leftUp.y()){return true;} else if(this-leftUp.y()block1.leftUp.y()){if(this-leftUp.x()block1.leftUp.x()){return true;}}return false;}
再就是平移重复检测
//检测平移重复性
int BlockDialog::checkTranslationRepeatability(BlockGroup *blockInfo1,BlockGroup *blockInfo2)
{//逐点进行坐标比较for(int i0;iblockInfo2-blockNum;i){if(blockInfo1-block[i].leftUp!blockInfo2-block[i].leftUp){//坐标不同return 0;}}return 1;//重复
}
最后是旋转重复检查比平移重复检测复杂一点的是有3次旋转90度、180度、270度。还有一点是旋转后的坐标如何确定好在我在坐标系上比划了一下旋转90度就是x,y - (y,-x)还是比较简单的
//将方块组进行顺时针旋转90度
int BlockDialog::RotateBlockGroup(BlockGroup *blockInfo){//1对整个方块组进行顺时针旋转90度Block blockTmpBlock();listBlock listBlock{};for(int i0;iblockInfo-blockNum;i){//旋转90度就是x,y - (y,-x)blockTmp.leftUp.setX(blockInfo-block[i].leftUp.y());blockTmp.leftUp.setY(0-blockInfo-block[i].leftUp.x());blockTmp.penColorblockInfo-block[i].penColor;//进行块组的赋值注意不能遗漏颜色属性blockTmp.brushColorblockInfo-block[i].brushColor;listBlock.push_back(blockTmp);}//2排序 -- 按什么顺序排列的//重载Block的比较操作符 顺序定义从左上角开始先第一排从左往右然后第二排listBlock.sort();//重新赋值int blockPos0;for(auto itlistBlock.begin();it!listBlock.end();it){blockInfo-block[blockPos]*it;blockPos;}adjustCoordinates(blockInfo);//调整坐标避免有负值坐标出现return 0;
}
//检测旋转重复性
int BlockDialog::checkRotaltionalRepeatability(BlockGroup *blockInfo1,BlockGroup *blockInfo2)
{for(int i0;i3;i){//每次旋转90度检查3次加之前的一次平移检查即完成了360度的检查//1对方块组旋转90度就是x,y - (y,-x)RotateBlockGroup(blockInfo2);//2先进行平移检测if(1checkTranslationRepeatability(blockInfo1,blockInfo2)){return 1;}}return 0;
}
至此就实现了循环遍历所有方块组合的主体功能。 然后将相关信息写入文件即可。
完整的代码可在如下链接地址获取 修改代码中方块组合中方块的个数
#define BLOCK_NUM 5 //4 //3 方块组内包含的方块个数
可以遍历获取不同个方块的组合类型。
