【Qt编程】Qt版扫雷-阿里云开发者社区

【Qt编程】Qt版扫雷

2014-04-10 1391

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 学习要学会举一反三。在以前的《用matlab扫扫雷》一文中，我用matlab简单的编写了一个扫雷小程序。当然，与Windows自带的扫雷程序自然是不敢相提并论。

学习要学会举一反三。在以前的《用matlab扫扫雷》一文中，我用matlab简单的编写了一个扫雷小程序。当然，与Windows自带的扫雷程序自然是不敢相提并论。今天我就用c++来写个扫雷程序，算是对c++的练习。在那篇文章中提过，扫雷问题是NP完全问题，不能被解决。网上也有人做过扫雷的辅助工具，但也只是指明肯定是雷、和肯定不是雷的位置，不能完全求解。 下面来讲述我的程序设计思路：
1.用随机数生成雷分布的矩阵，元素为0表示无雷，1表示有雷。
2.通过循环遍历来统计一个元素的周围与之相邻的8个元素的雷的个数。
3.当鼠标左击某个按钮时，如果有雷则游戏失败。如果没有雷且其周围8个位置雷的个数为0，则将周围的8个位置打开，如果这8个位置中还有元素的周围8个元素个数为0，则将它周围的8个位置打开，依次类推……。知道将所有雷都标记正确，游戏胜利。

游戏的缺点:
1.由于时间关系，没有对游戏的界面进行美化，因此界面比较简陋。
2.与Windows自带的扫雷相比，少了几点功能，如果学了QML可能效果会好一点，但是不影响正常使用。
3.没有对代码进行优化，代码可能显得冗余。

在编写过程中想到的：卷积的妙用
在统计一个元素与之相邻的8个元素的雷的总个数的时候，一般最容易想到的是用遍历来统计：
int x1,x2,x3,x4,x5,x6,x7,x8;//分别表示周围的8个位置的行
int y1,y2,y3,y4,y5,y6,y7,y8;//分别表示周围的8个位置的列
int count=0;//统计雷的个数
for(row=0;row<9;row++)
for(col=0;col<9;col++)
{
x1=row-1;y1=col-1;
x2=row-1;y2=col;
x3=row-1;y3=col+1;

x4=row;y4=col-1;
x5=row;y5=col+1;

x6=row+1;y6=col-1;
x7=row+1;y7=col;
x8=row+1;y8=col+1;

if(x1>=0&&y1>=0)//需要判断行和列是否越界
if( minefield[x1][y1]==1)
count=count+1;

if(x2>=0)
if( minefield[x2][y2]==1)
count=count+1;

if (x3>=0&&y3<9)
if (minefield[x3][y3]==1)
count=count+1;

if (y4>=0)
if (minefield[x4][y4]==1)
count=count+1;

if (y5<9)
if (minefield[x5][y5]==1)
count=count+1;

if(x6<9&&y6>=0)
if (minefield[x6][y6]==1)
count=count+1;

if(x7<9)
if (minefield[x7][y7]==1)
count=count+1;
if(x8<9&&y8<9)
if( minefield[x8][y8]==1)
count=count+1;
countnum[row][col]=count;
count=0;

}

上面的程序通俗易懂，但是需要经过多次的条件判断来保证数组的下标不越界。在matlab中我们可以通过一条语句则可以解决上述问题。

看下面的例子：

上图中，a就是雷的分布矩阵，1表示雷区。b是我们自己设置的一个特殊矩阵。c就是我们需要得到的雷的个数的矩阵，其中的含义如下：
c[0][0]=2,表示以a[0][0]为中心的九宫格中的雷的个数（自己的没有算在内）。那么c是如何得到的呢?正如上面所说，只需要一条命令即可：c=conv2(a,b,'same')。也就是求a矩阵和b矩阵的卷积！
当然矩阵的卷积我们在《信号与线性系统分析》中没有讲到，但是书中提到了一维向量的卷积。例如：
a=[1 2 3]; b=[4 5 6];
则a与b的卷积为c=conv(a,b)=[ 4 13 28 27 18];
具体的计算过程可以通过公式计算，下面用比较简单的方法来计算上面的卷积：

上面的计算方法和小学学的乘法好像一样，在我印象中，两个信号这样求卷积的前提好像是这两个信号都是因果信号，唉，具体是什么条件我也不是很清楚了。在这里来说，就不用管这些条件限制。
矩阵的卷积归根到底可以转换成一维向量的卷积，具体的做法是（以第一次的例子的值为例）：首先，将一个矩阵选择180度，这里我们选择b矩阵，碰巧b矩阵选择后的矩阵b1和原矩阵b一样;然后将b1矩阵每次往下移一行，将b1与a矩阵在同一行的一行分别进行一维向量的卷积运算，然后对应的列相加起来合并为一行。具体过程图解如下：

conv([1 0 1],[1 1 1])=[ 1 1 2 1 1 ]

conv([1 0 1],[1 0 1])+conv([1 1 1],[1 1 1])= [2 2 5 2 2]

conv([1 0 1],[1 1 1])+conv([1 1 1],[1 0 1])+conv([0 1 1],[1 1 1])= [2 3 6 4 3]

conv([1 1 1],[1 1 1])+conv([0 1 1],[1 0 1])=[ 1 3 4 3 2]

conv([0 1 1],[1 1 1])= [0 1 2 2 1]

综上所述：a与b的卷积是
1 1 2 1 1

2 2 5 2 2

2 3 6 4 3

1 3 4 3 2

0 1 2 2 1

这与c=conv2(a,b)的结果相同！而在我的扫雷程序中想要得到的是与a相同维数的矩阵，因此我们可以使用 c=conv2(a,b,'same')来得到我们的结果。

在前面的讨论中，我们使用的b矩阵是b=[1 1 1;1 0 1;1 1 1]。b的选取与我要的结果有关，如果我需要的是九宫格中所有的雷的个数（包含中心格），我们可以令b=[1 1 1;1 1 1;1 1 1];验证结果如下：