我正在准备KOI 2022，所以，我正在解决KOI 2021, 2020的问题。KOI 2020竞赛1第一期问题5(见这里的问题5)
我想让<vector<vector<int>> minesweeper(vector<vector<int>> &v)函数在5*5扫雷舰上工作。
参数
vector<vector<int>> &v
已转换为矢量的扫雷舰中的数字。
。{{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}}
Avector。大小与参数相同。我的是1，默认是0。
KOI 2020竞赛1第一期题目5的英文翻译
有一个5*5的扫雷拼图。
一共有11个数字，其余为空白。
0解决扫雷有两个简单的规则:
-
如果一个字段看到它所有的地雷，那么所有空白字段没有地雷，可以发现
-
如果一个字段有和缺少地雷一样多的空白字段，那么它们都包含地雷。
不断重复这些规则，直到没有任何变化。
现在它变得复杂了，因为您必须查看字段的组合。与其为2,3,4个已知字段找出许多特殊情况，我建议直接使用蛮力算法:
对于已知字段旁边的每个空白字段:
- 创建存在和不存在地雷的地图副本
- 返回顶部解决每个地图
- 如果其中一个地图导致任何已知领域没有看到足够的地雷，那么另一种情况必须是实际的解决方案，应用它并回到开始
如果没有进展，那么你必须猜测。上面的循环可以为你提供地雷位置的概率，如果你知道地雷的总数，你就有了其他空白字段的概率。选一个最不可能有矿的。