待你长发及腰

就问你们出题人够不够良心,出个简单广搜,而且数据还是很水的,写不对也有不少分

不会广搜的,或者不熟悉的先学学吧

题解配图纯手画┐(‘~`;)┌ ,凑活看吧QwQ

然后这题有不少解法,这里就只提供一种了

这道题呢,容易想到,搜索白棋联通块,同时统计周围的气数(即空白格数),然后对于气数为一的联通块,取大小最大的落子,

再加上开局已死的白棋个数,即ans=max{size of 联通块}+已死白棋数

但是想想就会发现,这么直接搜会有一些漏洞

比如这个:

可以看到,这个图中,我们在点1和点2会分别搜到空白,加一口气,这样下来就会有两口气

这个地方错了?估计你就没什么分了……

所以我们通过一个二维的breath数组来记录每个点是否曾被统计

气数的统计时,只统计还未被标记的点

那么经过仔细思考,问题又来了

如图:

在统计左侧联通块时,我们把两口气都标没了,然后右侧就视为没气了,显然是不对的

但是实测,这样是能拿60分的( ̄▽ ̄)~*

解决方案也不难想,我们可以开一个栈,把所有标没的气恢复,一次搜索结束后再把气标回来

在瞎凑一下,我们发现,还有一个小问题

再给张图:

在这张图中,最大一口气联通块个数为4,但是答案是7啊,堵住图中的气能杀敌人两片棋

但是表慌,错了也有90分

观察到这样一种性质,我们要统计的是只剩一口气的联通块,不妨把合法联通块大小作为权值挂到那个气的位置,

这样我们只需找出权值最大的位置就好了

所以,答案最终是ans=max{value of each position}+dead

原文地址:https://www.cnblogs.com/ivanovcraft/p/9567663.html