前言
数字华容道，记得以前《最强大脑》上一个初赛题目，正好最近家里买了个数字华容道的玩具，玩着还挺有意思，于是就想干脆自己做个华容道的游戏，本来说做这样的小游戏用Unity3D我觉得更好，无奈最近在自学Pytorch深度学习框架，装了Anaconda全家桶，硬盘空间告急，于是就把Unity3D给删了。想想不如用OpenCV做这个得了，正好算是针对OpenCV做了个综合实战。
实现效果
完整视频
设计思路
微卡智享
上图中是数字华容道的一个简单的操作流程思路，我们根据上面的流程设计逐步拆分进行思考：
01
生成数字华容道
因为做的是4X4的数字华容道，所以我们生成一个0-15的vector<int>数组，然后随机打乱顺序，存放到vector<vector<int>>的二维数据中（即4X4的矩阵），存其中0代表着可移动的空白位。
随机打乱数组代码
代码语言：javascript复制vector<int> Puzzles4x4::RandVectorNum()
{
vector<int> vts;
//定义华容道数字
vector<int> vtsnums{ 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };
int size = vtsnums.size();
for (int i = 0; i < size; i) {
//初始化随机数种子
srand((int)time(0));
int index = vtsnums.size() == 1 ? 0 : rand() % (vtsnums.size() - 1);
vts.push_back(vtsnums[index]);
//容器中删除已经赋值的数字
vtsnums.erase(vtsnums.begin() index);
}
return vts;
}02
绘制游戏图像
# | 思路 |
|---|---|
1 | 创建一个600X600的Mat，白底 |
2 | 根据4X4的矩形大小绘制整个棋盘的背景 |
3 | 每个格用Rect矩形绘制 |
4 | 对应Rect的数字显示用PutText函数 |
上面用到的OpenCV的函数主要就是rectangle和putText
03
鼠标操作
使用OpenCV的setMouseCallback回调事件，然后在OnMouse中设置了点击左键是移动，双击右键是重新开始游戏。
代码语言：javascript复制void onMouse(int event, int x, int y, int flags, void* param)
{
switch (event)
{
case EVENT_LBUTTONUP:
{
Point point = Point(x, y);
int col = -1;
int row = -1;
SelectVectorItem(point, contours, nummatrix, col, row);
if (col >= 0 && row >= 0) {
if (Puzzles4x4::VectorsMove(nummatrix, col, row)) {
if (isFinish) {
isFinish = false;
usetime = (double)getTickCount();
cout << "开始还原计时" << endl;
}
//重新生成图像显示
DrawPuzzlesMat(src, nummatrix, contours);
isFinish = Puzzles4x4::CheckFinished(nummatrix);
if (isFinish) {
usetime = ((double)getTickCount() - usetime) / getTickFrequency();
cout << "还原完成！用时：" << usetime << "秒！" << endl;
}
}
}
}
break;
case EVENT_RBUTTONDBLCLK:
{
//生成华容道
vector<int> tmpvets = Puzzles4x4::RandVectorNum();
Puzzles4x4::CreateNewGame(nummatrix, tmpvets);
//打印生成的华容道
Puzzles4x4::Printvectors(nummatrix);
//生成图像显示
DrawPuzzlesMat(src, nummatrix, contours, true);
//改变初始状态
isFinish = true;
}
break;
default:
break;
}
}鼠标左键移动
这一步为最核心的步骤，实现点击获取到对应的二维数组中数字的原理主要就是用到了OpenCV中的pointPolygonTest函数（计算点是否在轮廓内）。
以前使用OpenCV做轮廓查找时都是先定义vector<vector<Point>>，然后通过findContours的函数进行查找，因为这里我们是自己绘制的Rect矩形，所以我们在初次生成Rect的时候，就可以把每个一Rect的4个点存放到定义好的vector<vector<Point>>中，然后通过pointPolygonTest来判断点击的是第几个轮廓，获取到对应的行和列序号。
代码语言：javascript复制void InsertContours(vector<vector<Point>>& contours, Rect rect)
{
vector<Point> vetpt;
Point pt1 = Point(rect.x, rect.y);
vetpt.push_back(pt1);
Point pt2 = Point(rect.x rect.width, rect.y);
vetpt.push_back(pt2);
Point pt3 = Point(rect.x rect.width, rect.y rect.height);
vetpt.push_back(pt3);
Point pt4 = Point(rect.x, rect.y rect.height);
vetpt.push_back(pt4);
contours.push_back(vetpt);
}从上面获取到对应的行和列的序号的，就要开始计算是否可以进行移动，判断是否可以移动主要就是看点击的这个格，上下左右的方向中是否存在0的数字，如果不存在即不可移动，哪个方向为0，则直接和0的位置进行交换即可。
代码语言：javascript复制bool Puzzles4x4::VectorsMove(vector<vector<int>>& vts, int col, int row)
{
bool res = true;
//计算可移动的区域
//1.左边
if (col-1>=0 && vts[row][col-1]==0){
vts[row][col - 1] = vts[row][col];
vts[row][col] = 0;
}
//2.右边
else if (col 1 <= 3 && vts[row][col 1] == 0) {
vts[row][col 1] = vts[row][col];
vts[row][col] = 0;
}
//3.上边
else if (row 1 <= 3 && vts[row 1][col] == 0) {
vts[row 1][col] = vts[row][col];
vts[row][col] = 0;
}
//4.下边
else if (row - 1 >= 0 && vts[row - 1][col] == 0) {
vts[row - 1][col] = vts[row][col];
vts[row][col] = 0;
}
else {
res = false;
}
return res;
}
04
检测游戏是否完成
这个其实没有什么好说的，就是判断1-15每个数字是否在对应的格内即可。都在格内的时候0肯定是在右下角，所以我们检测函数先判断0是否在右下角，如果是的话再进行循环判断，这样可以减少循环次数，节省时间复杂度。
代码语言：javascript复制bool Puzzles4x4::CheckFinished(vector<vector<int>>& vts)
{
//计算总行数
int rows = vts.size() - 1;
//计算总列数
int cols = vts[rows].size() - 1;
//先判断最后一位是否是0，如果不是下面就不再浪费时间检查
if (vts[rows][cols] != 0) return false;;
int checknum = 1;
for (int row = 0; row <= rows; row) {
for (int col = 0; col <= cols; col) {
//最后一格已经检测，直接退出
if (col == cols && row == rows) return true;
if (vts[row][col] != checknum) return false;
checknum ;
}
}
}05
计时
这个直接采用OpenCV中的getTickCount()函数即可，当检测游戏完成时，计算一下总的用时输出。
重点说明
微卡智享
刚做完自己玩时，发现经常出现了这种无解的情况，后来通过查找相关的资料了解到：数字华容道NxN数字随机排列的阵列有解的必要条件是：N为奇数，总逆序数为偶数，N为偶数，总逆序数为奇数。
上面的数字排列：1 11 8 14 4 7 5 2 6 13 15 0 10 9 3 12。（0为空位）
计算得到的逆序对为：56
计算顺序：0 0 1 0 3 3 4 6 4 1 0 11 4 5 11 3 =56
得到的逆序对再加上0所以的行和列的位置：56 2(行号) 3(列号)=61
根据上面的结论NXN数字，N为偶数，总逆序数为奇数才有解，上面这个是没有问题的，如果为偶数，需要把最后两位数字调换一下位置即可。
计算逆序对
这个真是在LeetCode里面比较常见的题了，在我为数不多的刷题中还真刷过这个，主要是方法是暴力破解和分治思想。正好借着这个机会重新练习了一下分治思想的计算逆序对。
项目中CalcReversNum即计算逆序对的类
暴力破解
简单的双循环计算，代码简单，其实在我们这里面用这个最方便，因为始终是4X4的固定表格，计算量不会太大。
代码语言：javascript复制int CalcReverseNum::CheckCount(vector<int>& vts)
{
int count = 0;
for (int i = 0; i < vts.size(); i) {
cout << vts[i] << " ";
for (int j = 0; j < i; j ) {
if (vts[j] > vts[i]) count ;
}
}
return count;
}分治思想
分治思想的步骤：
（1）分解，将要解决的问题划分成若干规模较小的同类问题；
（2）求解，当子问题划分得足够小时，用较简单的方法解决；
（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。
#include "CalcReverseNum.h"
//静态变量需要在CPP文件中先初始化
vector<int> CalcReverseNum::tmpvts(1);
int CalcReverseNum::merge(vector<int> &vts, int left, int mid, int right)
{
//根据传入的数组调整静态变量的大小
tmpvts.resize(vts.size());
for (int i = left; i <= right; i )
tmpvts[i] = vts[i];
int i = left, j = mid 1, k= left;
int count = 0;
//遍历比较左右两个部分
while (i <= mid && j <= right) {
//左半部分元素小于右半部分的元素
if (tmpvts[i] <= tmpvts[j])
vts[k ] = tmpvts[i ];
else
{
//统计左半边能和右半边该元素构成的逆序对数
vts[k ] = tmpvts[j ];
count = mid - i 1;
}
}
while (i <= mid)
vts[k ] = tmpvts[i ];
while (j <= right)
vts[k ] = tmpvts[j ];
return count;
}
int CalcReverseNum::MergeSort(vector<int>& vts, int left, int right)
{
if (left >= right) return 0;
//通过分治思想取中间数再递归下去
int mid = left (right - left) / 2;
//递归排序左半部分
int leftnum = MergeSort(vts, left, mid);
//递归排序右半部分
int rightnum = MergeSort(vts, mid 1, right);
//计算当前部分
int nownum = merge(vts, left, mid, right);
return leftnum rightnum nownum;
}
源码地址
https://github.com/Vaccae/OpenCVNumPuzzles.git
点击下方的原文链接可以跳转到码云的源码地址。
