一些闲话

刚开始停课集训的时候准备\(CSP\)，觉得\(CSP\)拿\(20\)分进\(NOIP\)一定没问题。（因为国庆的\(Smeow\)出题太良心）所以我在摆烂。戴上耳机，开一个属于自己的（温柔的）世界。

然后就被老师撅了当面制裁了，她这么说的：“我昨天就说过，我们在机房累了玩下扫雷可以，就是不要玩大型游戏，这纯纯是浪费时间”

等等，我的世界算大型游戏嘛？（反正不要再玩了吧）

这里奉劝大家，游戏有风险，摆烂需谨慎。

那扫雷呢？拿来把你！

这不是摆烂，这是在练习\(BFS\)！！！

退役了，意犹未尽。

基本操作

不用我多说，人均会玩。

首先生成一张地图，长宽由你定，里面放置若干个雷。

为了游戏体验，第一次点击一定不能点到雷，（不然你怎么玩）所以要在第一次点击之后生成地图。

地图生成方式很简单，就是随一个坐标放雷。

但是在你第一次点到的点周围\(9\times9\)的范围里不能有雷，不然你第一次点到一个数字，你就只能靠你的运气来找雷了。

然后就是三种操作，左键（\(1\)），右键（\(2\)）和双击（\(3\)），不用我多说了吧。此外，我还加了一个自动排雷模式，不明白的可以微软商店下载新版扫雷自己体验一下。

算法

普普通通的\(BFS\)。别看我写\(200\)多行，其实核心部分就只有这么一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
char mp[maxn][maxm]; //用于输出的地图
bool isfl[maxn][maxm]; //是否放了旗子
bool ismi[maxn][maxm]; //是不是雷
bool vis[maxn][maxm]; //是否被搜到过
int mcnt[maxn][maxm]; //某个点周围雷的个数，即地图上显示的数字
int fcnt[maxn][maxm]; //某个点周围旗子的个数，排雷使用
int fy[8]={1,1,1,0,0,-1,-1,-1}; //向周围八个方向转移要加的偏移量
int fx[8]={1,0,-1,1,-1,1,0,-1};
int n,m,q; //地图的长宽和地雷的个数
bool bfs(int y,int x) //第y行第x列，习惯上我们用(x,y)坐标表示，这里在游戏中y轴正方向向下
{
    if(ismi[y][x]) return 1; //如果你点到雷，那抱歉了
    queue<pair<int,int> > q; //队列
    q.push(make_pair(y,x)); //起点入队
    while(!q.empty()) //当没有点可以扩展时退出
    {
        int yy=q.front().first;
        int xx=q.front().second; //取出坐标
        q.pop(); //弹出队首
        if(vis[yy][xx]) continue; //判断是否已经走过确认安全
        vis[yy][xx]=1;
        mp[yy][xx]='0'+mcnt[yy][xx]; //生成地图上的数字
        if(mcnt[yy][xx]==0) //只有当一个点周围没有雷时我们才可以向八个方向扩展
            for(int i=0;i<8;i++)
                if(yy+fy[i]>=0&&yy+fy[i]<n&&xx+fx[i]>=0&&xx+fx[i]<m&&!vis[yy+fy[i]][xx+fx[i]]&&!isfl[yy+fy[i]][xx+fx[i]]) //判断边界，判断是否有标记，判断是否走过
                    q.push(make_pair(yy+fy[i],xx+fx[i])); //入队
    }
    return 0;
}
随便来张图

简单来说，\(BFS\)就是由一个起点向外逐层扩展。它是由队列实现的（先进先出）

按照\(BFS\)的顺序，访问的节点依次是\(0,1,6,2,4,11,3,5,7,8,9,10\)，按照层数依次排列。

流程如下：首先将\(0\)加入队列，然后将与\(0\)直接相连的点加入队列，再将\(0\)弹出队列。每次我们从队首取出下一个要访问的节点，然后将与它直接相连且未被访问过的节点加入队尾，再弹出队首。这样在图连通时，既可保证节点不重不漏，又能保证访问到的节点是按离根节点的距离升序排列的。\(CSP-S2022\)第一题就用了它来求所有边权都为\(1\)时的最短路。此外，\(Dijkstra\)算法采用优先队列求单源最短路，\(01BFS\)采用双端队列求边权为\(0\)或\(1\)时的最短路，这些都可以看做\(BFS\)的变式，代码也都类似。

在扫雷中没有这样的图，我们可以将一个二维坐标设为起点，由它扩展周围的点，\(BFS\)实现。注意的细节：入队，出队，判断边界。

对于双击操作，在被双击的点周围标记的旗子数等于雷数时，玩家认为这个点周围没标记的点都是安全的，此时我们对周围没有标雷的点执行\(BFS\)。自动排雷，就是在插旗子时更新周围所有点的状态，如果发现可以进行双击操作，自动运行一遍双击操作。

代码

拒绝白嫖！看懂了请自己写一遍！

此代码为Windows下编写，Linux下有所区别，请自行修改
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
#include <bits/stdc++.h>
using namespace std;
namespace Kochi
{
    const int maxn=24,maxm=30,maxq=504;
    char mp[maxn][maxm];
    bool isfl[maxn][maxm];
    bool ismi[maxn][maxm];
    bool vis[maxn][maxm];
    int mcnt[maxn][maxm];
    int fcnt[maxn][maxm];
    int fy[8]={1,1,1,0,0,-1,-1,-1};
    int fx[8]={1,0,-1,1,-1,1,0,-1};
    int n,m,q;
    bool bfs(int y,int x)
    {
        if(ismi[y][x]) return 1;
        queue<pair<int,int> > q;
        q.push(make_pair(y,x));
        while(!q.empty())
        {
            int yy=q.front().first;
            int xx=q.front().second;
            q.pop();
            if(vis[yy][xx]) continue;
            vis[yy][xx]=1;
            mp[yy][xx]='0'+mcnt[yy][xx];
            if(mcnt[yy][xx]==0)
                for(int i=0;i<8;i++)
                    if(yy+fy[i]>=0&&yy+fy[i]<n&&xx+fx[i]>=0&&xx+fx[i]<m&&!vis[yy+fy[i]][xx+fx[i]]&&!isfl[yy+fy[i]][xx+fx[i]])
                        q.push(make_pair(yy+fy[i],xx+fx[i]));
        }
        return 0;
    }
    int Ayatsuki()
    {
        printf("Stickman的扫雷\n");
        system("color ed");
        system("pause");
        while(1)
        {
            system("cls");
            printf("选择难度\n");
            printf("1为简单,2为中等,3为困难,4为自定义\n");
            printf("输入其他数字退出游戏\n");
            int choice;
            scanf("%d",&choice);
            switch(choice)
            {
                case 1:
                    n=9,m=9,q=10;
                    break;
                case 2:
                    n=16,m=16,q=40;
                    break;
                case 3:
                    n=16,m=30,q=99;
                    break;
                case 4:
                    while(1)
                    {
                        printf("请输入高度：\n");
                        scanf("%d",&n);
                        printf("请输入宽度：\n");
                        scanf("%d",&m);
                        printf("请输入地雷数：\n");
                        scanf("%d",&q);
                        if(n>=9&&n<=maxn&&m>=9&&m<=maxm&&q<=maxq&&q<=n*m-9)
                            break;
                        else
                            printf("非法输入\n");
                    }
                    break;
                default:
                    return 0;
            }
            printf("输入1开启自动排雷,输入0取消\n");
            int at;
            scanf("%d",&at);
            system("cls");
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<m;j++)
                {
                    mp[i][j]='#';
                    putchar(' ');
                    putchar(mp[i][j]);
                }
                putchar('\n');
            }
            memset(isfl,0,sizeof(isfl));
            memset(ismi,0,sizeof(ismi));
            memset(vis,0,sizeof(vis));
            memset(mcnt,0,sizeof(mcnt));
            memset(fcnt,0,sizeof(fcnt));
            printf("选择起始位置,先列后行\n");
            int y,x;
            scanf("%d%d",&x,&y);
            while(y<1||y>n||x<1||x>m)
            {
                printf("非法输入\n");
                printf("选择起始位置,先列后行\n");
                scanf("%d%d",&x,&y);
            }
            mt19937 mt_rand(time(0));
            for(int i=1;i<=q;i++)
            {
                int yy=mt_rand()%n,xx=mt_rand()%m;
                while(ismi[yy][xx]||(abs(yy+1-y)<2&&abs(xx+1-x)<2))
                    yy=mt_rand()%n,xx=mt_rand()%m;
                ismi[yy][xx]=1;
                for(int j=0;j<8;j++)
                    if(yy+fy[j]>=0&&yy+fy[j]<n&&xx+fx[j]>=0&&xx+fx[j]<m)
                        mcnt[yy+fy[j]][xx+fx[j]]++;
            }
            bfs(y-1,x-1);
            int op;
            while(1)
            {
                system("cls");
                for(int i=0;i<n;i++)
                {
                    for(int j=0;j<m;j++)
                    {
                        putchar(' ');
                        putchar(mp[i][j]);
                    }
                    putchar('\n');
                }
                printf("请输入操作\n");
                printf("1点开2插拔旗3排雷\n");
                scanf("%d",&op);
                printf("请输入位置,先列后行\n");
                scanf("%d%d",&x,&y);
                while(op<1||op>3||y<1||y>n||x<1||x>m)
                {
                    printf("非法输入\n");
                    printf("请输入操作\n");
                    printf("1点开2插拔旗3排雷\n");
                    scanf("%d",&op);
                    printf("请输入位置,先列后行\n");
                    scanf("%d%d",&x,&y);
                }
                if(op==2)
                {
                    if(vis[y-1][x-1])
                        continue;
                    mp[y-1][x-1]=isfl[y-1][x-1]?'#':'P';
                    isfl[y-1][x-1]^=1;
                    for(int i=0;i<8;i++)
                        if(y-1+fy[i]>=0&&y-1+fy[i]<n&&x-1+fx[i]>=0&&x-1+fx[i]<n)
                        {
                            isfl[y-1][x-1]?fcnt[y-1+fy[i]][x-1+fx[i]]++:fcnt[y-1+fy[i]][x-1+fx[i]]--;
                            if(isfl[y-1][x-1]&&at)
                            {
                                if(fcnt[y-1+fy[i]][x-1+fx[i]]<mcnt[y-1+fy[i]][x-1+fx[i]]||ismi[y-1+fy[i]][x-1+fx[i]]||isfl[y-1+fy[i]][x-1+fx[i]])
                                    continue;
                                for(int j=0;j<8;j++)
                                    if(y-1+fy[i]+fy[j]>=0&&y-1+fy[i]+fy[j]<n&&x-1+fx[i]+fx[j]>=0&&x-1+fx[i]+fx[j]<n&&!isfl[y-1+fy[i]+fy[j]][x-1+fx[i]+fx[j]]&&!vis[y-1+fy[i]+fy[j]][x-1+fx[i]+fx[j]])
                                        if(bfs(y-1+fy[i]+fy[j],x-1+fx[i]+fx[j]))
                                            goto violet;
                            }
                        }
                }
                if(op==3)
                {
                    if(fcnt[y-1][x-1]<mcnt[y-1][x-1]||!vis[y-1][x-1])
                        continue;
                    for(int i=0;i<8;i++)
                        if(y-1+fy[i]>=0&&y-1+fy[i]<n&&x-1+fx[i]>=0&&x-1+fx[i]<n&&!isfl[y-1+fy[i]][x-1+fx[i]]&&!vis[y-1+fy[i]][x-1+fx[i]])
                            if(bfs(y-1+fy[i],x-1+fx[i]))
                                goto violet;
                }
                if(op==1)
                {
                    if(vis[y-1][x-1]||isfl[y-1][x-1])
                        continue;
                    if(bfs(y-1,x-1))
                    {
                        violet:
                        system("cls");
                        for(int i=0;i<n;i++)
                        {
                            for(int j=0;j<m;j++)
                            {
                                putchar(' ');
                                if(ismi[i][j]&&mp[i][j]=='P') putchar('P');
                                else if(!ismi[i][j]&&mp[i][j]=='P') putchar('d');
                                else if(ismi[i][j]) putchar('*');
                                else putchar(mp[i][j]);
                            }
                            putchar('\n');
                        }
                        printf("你输了\n");
                        system("pause");
                        break;
                    }
                }
                bool isover=1;
                for(int i=0;i<n;i++)
                    for(int j=0;j<m;j++)
                        if(!vis[i][j]&&!ismi[i][j])
                            isover=0;
                if(isover)
                {
                    system("cls");
                    for(int i=0;i<n;i++)
                    {
                        for(int j=0;j<m;j++)
                        {
                            putchar(' ');
                            if(ismi[i][j]&&mp[i][j]=='P') putchar('P');
                            else if(ismi[i][j]) putchar('*');
                            else putchar(mp[i][j]);
                        }
                        putchar('\n');
                    }
                    printf("你赢了!!!\n");
                    system("pause");
                    break;
                }
            }
        }
        return 0;
    }
}
int main()
{
    return Kochi::Ayatsuki();
}
//g++ minesweeper.cpp -o minesweeper.exe -O2 -std=c++14 -static