一个导致 C 题 62.07 或 65.53 分的坑点
解题方法不再赘述,题解讲的比较清楚,核心就是将连通块内边界染成红色,外边界染成白色。
某个点在不在连通块内就是以此点为起点,在水平或垂直方向上发射一条射线,找到第一个有颜色的点就可以判断答案。
此时很多人会有疑惑,为什么水平/垂直方向都要判断,按逻辑来说只要判断一个方向就足够了。
正确性是对的,但问题出在染色的时候。
对于某个连通块里的雷,我们应该将其忽略,问题就出在忽略雷的过程中。
一个应当被染成红色的位置,可能因为能把它染成红色的雷被忽略了,导致它被其他没忽略的雷当成外侧点染成了白色。
所以必须要两个方向都检查来确保内边界被正确染色。
而查询的时候因为已经被染好色了,所以只查一个方向正确性倒是能保证的。
呈现这两种分数的人大都是只查了行或者列,翻了一下提交记录有不少人有这个问题,故以此警示()
查看14道真题和解析