C＆＃x2B;＆＃x2B; [KOI 2020]中的Minesweeper算法
我正在准备锦鲤2022，所以，我正在解决KOI 2021、2020问题。 KOI 2020竞赛1第1期问题5（请参阅在这里）
我想制作＆lt; vector＆lt; vector＆lt; int＆gt;＆gt; Minesweeper（Vector＆lt; vector＆lt; int＆gt;＆gt;＆amp; v）功能，可在5*5 Minesweeper上使用。
参数
vector＆lt; vector＆lt; int＆gt;＆gt; ＆amp; v
在扫雷器中转换为矢量的数字。 -1如果是空白。
例如{{0，0，1，-1，1}，{-1，3，3，3，-1，1}，{-1，-1，-1，-1，1，0}，{2 ，5，-1、3，-1}，{-1，-1，-1，-1，-1}}
返回值
a vector。大小与参数相同。我的是1，默认值为
0
。
有11个数字，其他数字为空白。
| 0 | 0 | 1 | 가 | 1 |
|---|---|---|---|---|
| 나 | 33 | | 1 | |
| 다 | 02 | |||
| 5 | | 3 | ||
| 라 | 마마 |
mine
A.
b.b.c.
다
d.e
E.
가 我也想要算法描述。
I'm preparing KOI 2022, so, I'm solving KOI 2021, 2020 problems. KOI 2020 contest 1 1st period problem 5(See problem 5 in here)
I want to make <vector<vector<int>> minesweeper(vector<vector<int>> &v) function that works on 5*5 minesweeper.
argument
vector<vector<int>> &v
Numbers in minesweeper that converted to vector. -1 if it is blank.
e.g. {{0, 0, 1, -1, 1}, {-1, 3, 3, -1, 1}, {-1, -1, -1, -1, 0}, {2, 5, -1, 3, -1}, {-1, -1, -1, -1, -1}}
return value
A vector. Size is same with argument. Mine is 1, default is 0.
English translation of KOI 2020 contest 1 1st period problem 5
There is a 5*5 minesweeper puzzle.
There are 11 numbers, and the others are blank.
| 0 | 0 | 1 | 가 | 1 |
|---|---|---|---|---|
| 나 | 3 | 3 | 1 | |
| 다 | 0 | |||
| 2 | 5 | 3 | ||
| 라 | 마 |
Where is the mine?
A. 가
B. 나
C. 다
D. 라
E. 마
How can I make minesweeper function? I want algorithm description, too.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
有两个简单的规则来解决扫雷器：
如果一个字段看到了所有地雷，那么所有空白处都没有地雷，并且可以被发现。
如果一个字段的空白处与缺少矿山一样多，则它们都包含地雷。
不断地应用这些规则，直到什么都没有改变。
现在它变得复杂，因为您必须查看字段的组合。我建议直接进入蛮力算法，而不是弄清楚很多特殊案例：
对于一个知识字段旁边的每个空白字段：
如果没有取得进展，则必须猜测。上述循环可以为您提供矿山所在地点的概率，如果您知道总矿山的数量，则您对其他空白字段的可能性。选择最不可能有一个矿山的可能性。
There two some simple rules to solving Minesweeper:
If a field sees all it's mines then all blank fields don't have mines and can be uncovered.
If a field has as many blank fields as it is missing mines then they all contain mines.
Keep applying those rules over and over till nothing changes.
Now it gets complex because you have to look at combinations of fields. Instead of figuring out lots of special cases for 2, 3, 4 known fields I suggest going straight to a brute force algorithm:
For every blank field next to a know field:
If no progress was made then you have to guess. The above loop can give you probabilities for where mines are and if you know the number of mines total you have a probability for other blank fields. Pick one least likely to have a mine.