扫雷游戏算法设计与实现

文章目录[x]
  1. 1:实现扫雷程序
  2. 1.1:思路
  3. 1.2:代码
  4. 2:智能扫雷算法设计与实现
  5. 2.1:思路
  6. 2.2:代码
  7. 3:图形界面扫雷游戏的实现
  8. 3.1:代码
  9. 4:遇到的问题及解决方法
  10. 5:运行结果

实现扫雷程序

Time Limit: 4000MS                                        Memory Limit: 512MB

请编写程序从初始界面开始,对于一系列用户的点击,求出点击之后的游戏界面。未打开的 方格用-1 表示,即游戏初始时为 n 行 m 列-1。已打开且未与雷相邻的方格用 0 表示,已打开 且与雷相邻的方格用数字 a(1≤a ≤8)表示,即与之相邻的地雷数。

输入格式:

输入第一行是 4 个正整数 n、m、k 和 l,其中 n、m、k 的含义如前所述。接下来 k 行,每行 2 个整数 i 和 j,表示每个雷的坐标,即雷在第 i 行第 j 列的方格里。接下来 l 行,每行 2 个整 数 i 和 j,表示用户点击信息,即用户点击了第 i 行第 j 列的方格。m, n 不超过 20,k 不超过 50,l 不超过 200,0 ≤ i < n,0 ≤ j < m。

输出格式:

对于用户的每个点击:(1)如果用户点击的方格是已被打开的方格,则点击无效,忽略该点击。 (2)如果点击的方格是地雷,则输出“You lose”,程序退出;(3)如果点击的方格不是地雷, 则输出点击后的游戏界面,即 n 行 m 列空格间隔的整数,此时若用户获胜,则再输出“You win”。注:对用户每个有效点击所输出的信息用一个空行间隔。

样例:

输入

输出

5 5 1 1

0 0
4 4

-1 1 0 0 0

1 1 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

You win

4 5 1 2

1 2
3 0
1 2

0 1 -1 1 0

0 1 -1 1 0

0 1 1 1 0

0 0 0 0 0

You lose

4 5 1 2

1 2
3 0
0 2

0 1 -1 1 0

0 1 -1 1 0

0 1 1 1 0

0 0 0 0 0

 

0 1 1 1 0

0 1 -1 1 0

0 1 1 1 0

0 0 0 0 0

You win

 

提交方式:

学生通过在线评测系统 jlu.openjudge.cn 提交代码,别忘了用自己真名,并选定班级。 评测方法:

该小题满分 30 分,为全自动评测。本题不采用上学期的 ACM 竞赛规则,而是采用 OI 竞

赛规则,该题后台共 6 组测试数据,上学期是必须 6 组全过才算通过;而本次是每组数据 5 分, 6 组数据全部通过可得 30 分,只过 5 组则得 25 分,过 4 组得 20 分,以此类推。提交后是 Accepted 则得满分,若是 Wrong Answer,则将页面拉到最下边,能看到自己本次提交的具体 得分。可以多次提交,以最后一次提交为准。并不是很看重题目完成的时间。

思路

利用递归结构,向四周扩散,对符合条件的格子进行打开操作

重点是对于递归执行的判断,若不对其进行判断,则对于一个展开区域,其中的每个点都会展开到整个区域,展开的点在展开过程中又会执行新的递归,这会导致函数进入死循环,无法跳出,所以合理的递归出口和递归入口的判断是极有必要的。

对每一个递归到的格子执行判断:若这个格子没有被打开过,则进行递归,否则不执行递归,前进到下一个点再进行此判断。这样可以使得递归程序更加高效地运行,并且避免了死循环的情况。

代码

//
//  main.cpp
//  data structure 1st.
//
//  Created by 杜逸凡 on 2020/2/26.
//  Copyright © 2020 杜逸凡. All rights reserved.
//

#include <iostream>
#include <vector>
using namespace std;

struct unit{
    bool opened;
    int mine_count;
    bool mine;
};

int mine_count(int n,int m,vector<vector<unit*>> &data){
    int count=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(data[i][j]->opened)
                count++;
    return n*m-count;
}

void scan(int stepa,int stepb,int n,int m,vector<vector<unit*>> &data){
    data[stepa][stepb]->opened=true;
    if(data[stepa][stepb]->mine || data[stepa][stepb]->mine_count!=0){
//        set_open_surround(stepa, stepb, n, m, data);
        data[stepa][stepb]->opened=true;
        return;
    }else{
        if(stepa-1>=0 && stepb-1>=0 && data[stepa-1][stepb-1]->opened==false)
            scan(stepa-1, stepb-1, n, m, data);
        if(stepa-1>=0 && stepb>=0 && data[stepa-1][stepb]->opened==false)
            scan(stepa-1, stepb, n, m, data);
        if(stepa-1>=0 && stepb+1<m && data[stepa-1][stepb+1]->opened==false)
            scan(stepa-1, stepb+1, n, m, data);
        if(stepa>=0 && stepb-1>=0 && data[stepa][stepb-1]->opened==false)
            scan(stepa, stepb-1, n, m, data);
        if(stepa>=0 && stepb+1<m && data[stepa][stepb+1]->opened==false)
            scan(stepa, stepb+1, n, m, data);
        if(stepa+1<n && stepb-1>=0 && data[stepa+1][stepb-1]->opened==false)
            scan(stepa+1, stepb-1, n, m, data);
        if(stepa+1<n && stepb>=0 && data[stepa+1][stepb]->opened==false)
            scan(stepa+1, stepb, n, m, data);
        if(stepa+1<n && stepb+1<m && data[stepa+1][stepb+1]->opened==false)
            scan(stepa+1, stepb+1, n, m, data);
    }
}

void minecount_set(int stepa,int stepb,int n,int m,vector<vector<unit*>> data){
    if(stepa-1>=0 && stepb-1>=0)
        data[stepa-1][stepb-1]->mine_count++;
    if(stepa-1>=0 && stepb>=0)
        data[stepa-1][stepb]->mine_count++;
    if(stepa-1>=0 && stepb+1<m)
        data[stepa-1][stepb+1]->mine_count++;
    if(stepa>=0 && stepb-1>=0)
         data[stepa][stepb-1]->mine_count++;
    if(stepa>=0 && stepb+1<m)
         data[stepa][stepb+1]->mine_count++;
    if(stepa+1<n && stepb-1>=0)
         data[stepa+1][stepb-1]->mine_count++;
    if(stepa+1<n && stepb>=0)
         data[stepa+1][stepb]->mine_count++;
    if(stepa+1<n && stepb+1<m)
         data[stepa+1][stepb+1]->mine_count++;
}

void print(int n,int m,vector<vector<unit*>> data){
    for (int j=0; j<n; j++) {
        for(int k=0;k<m;k++){
            if(!data[j][k]->opened)
                cout<<"-1 ";
            else
                cout<<data[j][k]->mine_count<<' ';
        }
        cout<<endl;
    }
}

int main(int argc, const char * argv[]) {
    int n,m,k,l;
    int a,b;
    cin>>n>>m>>k>>l;
    vector<vector<unit*>> data;
    vector<pair<int, int>> step;
    vector<pair<int, int>> mine;
    for(int i=0;i<k;i++){
        cin>>a>>b;
        pair<int, int> node(a,b);
        mine.push_back(node);
    }
    for(int i=0;i<l;i++){
        cin>>a>>b;
        pair<int, int> node(a,b);
        step.push_back(node);
    }
    for(int i=0;i<n;i++){
        vector<unit*>data_node;
        for(int j=0;j<m;j++){
            unit *node=(unit*)malloc(sizeof(unit));
            node->opened=false;
            node->mine_count=0;
            node->mine=false;
            data_node.push_back(node);
        }
        data.push_back(data_node);
    }
    for(int i=0;i<k;i++){
        int a=mine[i].first;
        int b=mine[i].second;
        data[a][b]->mine=true;
        minecount_set(a,b,n,m,data);
    }
    for(int i=0;i<l;i++){
        int a=step[i].first;
        int b=step[i].second;
        if(data[a][b]->mine && i==0){
            print(n,m,data);
            cout<<"You lose";
            return 0;
        }else if(data[a][b]->mine){
            cout<<"You lose";
            return 0;
        }else if(data[a][b]->opened){
            continue;
        }else{
            scan(a, b, n, m, data);
            print(n,m,data);
            if(i==l-1 && mine_count(n, m, data)==k){
                cout<<"You win";
                return 0;
            }else
                cout<<endl;
        }
    }
    return 0;
}

智能扫雷算法设计与实现

请继续编写程序,帮助(替代)玩家自动扫雷,用尽可能少的步数最快完成扫雷。请注意,作为玩家,你的程序并不知道地雷的实际位置。本小题无需编写整个程序,只需实现如下函数:

void machine(int GamePanel[30][30], int n, int m, int &x, int &y);

该函数功能为读入当前游戏界面,并给出决策结果,即在当前游戏界面下,下一步应该点击哪个方格。其参数含义为:数组 GamePanel[][]存储 n 行 m 列整数,表示当前游戏界面,数组中数值的含义同(1)小题。x、y 表示下一步应点击的方格的行号和列号,0  x< n,0  y< m。也就是说,x 和 y 即本函数的决策结果,表示在当前游戏界面下,应该点击哪个方格。注意在本题中,machine 函数并不知道后台地雷的实际位置,只能根据当前的游戏界面进行决策。

提交方式:

请同学们通过“超星平台”以“交作业”的方式提交你编写的函数:将你编写的函数存入文本文件中,文件名为“班级-姓名.txt”,如“5 班-张无忌.txt”,以附件形式提交。注意 machine函数一定严格按照上述接口,函数名和参数不允许有任何改动。若 machine 函数中调用了你自定义的其他函数,则其他函数也须提交,并放在 machine 函数之前。

评测方法:

该小题满分 60 分,半自动评测。老师编写了评测程序,评测程序采用 20*20 的游戏界面,包含随机放置的 50 个地雷。评测程序不断调用 machine 函数,向其传送当前游戏界面GamePanel,并获取下一步应点击的方格坐标 x 和 y,并进行点击。直至游戏结束或点击次数超过 400 次。评测程序仅包含 iostream.h、stdio.h、time.h、stdlib.h、math.h 头文件,即你的 machine 函数只允许使用这些头文件内的库函数。老师收集本班学生代码,将代码放入评测程序中,在本地运行评测程序得出每名同学的分数。

分数计算方法如下:

➢ 如果扫雷失败或点击次数超过 400 次游戏仍未结束:得分=总共打开的方格数/10

即打开的格子越多得分越多,因为有 400 个方格,50 个地雷,所以最多能打开 350 个方

格,也就是说扫雷失败得分不会超过 35 分。

➢ 如果扫雷成功:得分=50+bonus

其中????? ={

10 , 0<???<60

9 , 60≤???<80

8 , 80≤???<100

7 , 100≤???<120

5 , 120≤???<150

3 , 150≤???<200

1 , 200≤???<250

0 , ???≥250

}

cnt 为有效点击数,例如在点击 60 次以内完成扫雷,则得 60 分。即用越少的步数完成扫 雷者得分越高,扫雷成功至少得 50 分,至多得 60 分。

➢ 若提交的代码放入评测程序后编译失败、无法正常运行或运行时间超过 30 秒:得分=0

➢ 为公平起见,评测程序将进行 5 次完整游戏,取你得分最高的 1 次作为最终成绩。

注:现评测规则已经修改为运行十次取平均分*1.3,所以想要得高分,首要任务就是要保证胜率,其次才是尽可能减少步数

提示:

本题没有标准答案,同学们可以充分发挥想象力给出可能的解法。任何基础、任何层次的同学都有能力给出解答。比如实在想不出好办法的同学,可以随机选择一个方格,即相当于在游戏盘面上随机点击方格,这样虽然很难成功完成扫雷,但至少能打开一定数量的格子,获得一定分数。对于有较好编程基础的同学,可以思考一下,你在实际玩这个游戏的时候,是怎么玩的,采用什么策略,那么就可以把该策略编程实现出来。自己想在本地测试 machine 函数的效率怎么办?可以自己编写一个主程序,也可以利用接下来的(3)小题。

思路

在进行多轮扫雷游戏后,我发现人玩扫雷都会去现寻找一个特定的格子,这个格子的周围除了雷所在的格子其他的格子全部打开了,即这个格子所标记的数字和他周围没有打开的格子数量相等,在标记过这个格子周围的雷后,就可以以此为突破点进行展开式的全图推算,从而完成整局游戏。于是我打算模拟人类在玩扫雷游戏时的思维,先找到特殊格子,再通过这个格子进行推算。

对于雷的存储,为了模拟在实际游戏中的旗子(即对可能是雷的地方进行标记),在函数中会设立一个数组用来存储雷的位置。 之后的函数按照人类思维逐个格子进行判断。

在无法进行简单判断后,引入扫雷的减法公式。 减法公式就是指两个相邻方格(以左右相邻为例)左边方格的左侧三个格子里的雷数减去右边方格右侧三个格子里的雷数等于左边格子的数值减去右边格子的数值。

对于格子(x,y)和(x,y+1)

Mine((x-1,y-1),(x,y-1),(x+1,y-1))-Mine((x-1,y+2),(x,y+2),(x+1,y+2))=GamePanel[x][y]-GamePanel[x][y+1]

对于上图,A中雷数-B中雷数=M数值-N数值Mine(A)-Mine(B)= M – N

使用减法公式判断是否有可以确定的格子,标记或打开。

扫雷公式详情请见:扫雷进阶玩家判雷核心——减法公式的应用实例(修正版)

链接:https://zhuanlan.zhihu.com/p/28176578

当减法公式也无法确定的时候,进行概率统计,每个格子的雷概率为周围未确定方格剩余未确定雷数除以周边未打开方格数的叠加,遍历选择概率最小的。统计方法如下图所示:

对于一个数值为3的方块,有三个未知雷,周围有8个未知方块,则每个方块为雷的概率为3/8

对于另一个数值为4的方块,周围已知一个雷,有3个雷未知,周围有7个未知方块(一个雷已知)对于他周边的方块来说是雷的概率为3/73,4方块相交界的地方是雷的概率为两个方块的概率相叠加,即对于方块3的概率3/8加上对于方块4的概率3/7,p=3/8+3/7三个方块相交至多个方块相交以此类推,可以计算出每个方块为雷的概率

若还无法确定安全位置,进入随机数阶段,并对随机数所指位置进行判断,为雷则重新随机,不为雷则传出。

代码

太长就不放出来了

图形界面扫雷游戏的实现

前两小题已经完成了扫雷的核心算法,但均为控制台程序,运行结果不够直观。为此老师向同学们提供扫雷游戏的图形界面框架(附件 2,开发环境 Visual Studio 2017),大家无需掌握图形界面编程技术,只需按接口要求,将自己编写的(1) (2)小题程序放入框架,即可编译生成图形界面游戏,具体方法如下:

① 将(1)题中的核心功能封装成如下函数:

int RefreshGamePanel(int GamePanel[30][30], int x, int y, int mine[30][30], int n, int m, int k)

该函数功能是根据当前游戏界面和玩家点击的方格,给出点击之后的游戏界面。

各参数含义为:数组 GamePanel[][]存储 n 行 m 列整数,表示当前的游戏界面,x 和 y 表示玩家点击的方格坐标,即第 x 行第 y 列的方格,0 ≤ x< n,0 ≤ y< m。数组 mine[][]存储地雷的信息,若第 i 行第 j列有雷则 mine[i][j]=1,否则 mine[i][j]=0,k 为雷的总数。该函数根据玩家点击的方格,按照游戏规则更新 GamePanel[][]数组。函数返回值表示游戏是否结束:若玩家点中的方格是雷,则游戏以失败结束,函数返回-1;若玩家点击方格后,所有非雷方格都被打开,则游戏以获胜结束,函数返回 1;若点击方格后游戏未结束,则返回 0。

点击 Cbutton.sln 文件打开整个项目,将 RefreshGamePanel 函数和(2)小题实现的 machine函数放入 CButtonView.cpp 文件中,具体位置已在该文件中标出。

③ 若你的函数中还调用了自定义的其他函数,则这些函数也须一并放入 CButtonView.cpp。也可将该图形界面游戏作为开发(1)(2)时的测试之用。在已打开的方格处点击鼠标右键, 可显示雷的真实位置,进而可以测试你的 RefreshGamePanel 和 machine 函数是否正确。老师给出一个简单示例,请见附件 3。

代码

无,将前两问函数加入老师所给的CButtonView.cpp即可

注:第一问函数核心部分需要安老师提供的格式封装

遇到的问题及解决方法

首要问题就是如何存储整个棋盘的各种属性,鉴于一个格子有多个不同属性,我采用了结构体指针数组来进行存储,三个属性分别为:周围雷数,是否打开,是否为雷。(在后面的题目中发现了使用两个数组来存储所需空间更少)

对于雷的记数,采用的是每设置一个雷,对这个格子的p8临域里的雷记数分别进行count++操作的方法。

解决了数据的存储问题和雷的初始化问题后就要解决最重要的核心函数了——点击后展开区域的函数。正如一中所说,这个函数用递归实现很方便,当碰到雷方块或非0方块时,跳出递归;当到达一个新点时,若该点已经打开,则前进到下一个点再次进行判断是否打开,若未打开,在该点执行递归程序。

在程序执行的时候发现递归程序会在执行过程中出现数组访问越界的情况,经过检查后发现一开始的程序并未考虑边界问题,即展开到边界后并未停下,并出现了诸如[-1][-1]这样的访问方式,于是在递归入口加入了边界判断,问题解决。

对于machine函数,遇到过位置并未按照所设置的程序输出,因为并不熟悉VS的使用以及老师所给框架的调试(如cout等常规方法无用),在询问同学和上网查询后,使用了MessageBox来对程序逐点进行调试,最终发现问题为某一函数参数传入错误,改正后可正常运行。

部分调试数据

运行结果

点赞

发表评论