3173. 【GDOI2103模拟3.17】扫雷游戏(搜索 + 剪枝)

Problem

给出一个类似扫雷的游戏,有\(num\)个数字,求至少有多少个雷。

Data constraint

\(n,m\le 15,num\le 15\)

Solution
  • 好搜索啊。

  • 现讲一种自己的方法:

    显然是贪心了。就把当前局面中较优的点先选,什么是较优呢?可以看成一个估价函数,你估价一下选这个点能给多少个数字减一,越多当然越好。当然,这个估价太弱了。。。

    我们还有另外一种估价方法:估价一个点身边的数字的“紧迫程度”,即如果这个点不选,可能周边一个数字就不合法了,一个点对它周围的数字越紧迫,我们越要选。具体的,我们用 原数字 - 还剩格子数 作为一个数字的紧迫程度,累加一下。

    当然,最后讲一种极其牛逼的估价方法:把每个数字的剩余数加到它周边的格子去。(目前找不到能卡的数据。。。)

    最后,如果怕被卡,可以这三种方法一齐上,每种都卡一下时,然后取个\(min\),注意我们搜索的时候,如果搜到一个解,就不继续往下搜,这样不能保证答案最优,但可以保证答案很优。

  • 再说一下题解的方法:

    实质上是个状压,但我觉得很悬。。把本质相同的点缩起来,然后枚举选的个数,然后类似搜索一样做就好。

上一篇:Linux系统安全配置基线


下一篇:mysql in 命令