题解 P2156 【[SDOI2009]细胞探索】

· · 题解

我大SD竟然出过这样的糟题

要是省选中出这样的题的话肯定当场疯掉

直接回正题吧

我们把细胞质(就是‘.‘ 下文用质代替）和非细胞质(就是’#‘ 下文用非质代替)分别BFS求一遍连通块

其中对于质求的连通块是四联通，非质求的块是八连通，然后给连通块编号

并记录下一些性质

什么性质下文再说

对于一个质，如果它只与两个非质连通块相接

而且这个质不延伸到给的矩阵边界（就是不被非质围起来的)

并且那两个相接的非质连通块满足一个有核的性质，一个有细胞膜的性质

那么这就是一个完整的细胞

对于一个质是否能延伸到边界且是否与刚好两个不同的非质连通块相接，这个可以在第一遍BFS中维护出来

对于一个非质是否有核和细胞膜，有点麻烦

一个非质连通块满足核的性质，当且仅当：

1.只与一个质连通块相接，且这个质连通块不会延伸到边界

2.它的四联通的遍历等价于它的八连通的遍历

这两个可以额外一次BFS求出来

一个非质连通块满足细胞膜的性质，等价于

对于这个的判断我们可以保留每个连通块最上面的点的纵坐标（从上到下从1到N)

若质最上纵坐标>该非质最上横坐标&&这个质不延伸到边界 那么这个质就在这个非质里面

这个也可以开头预处理+再一个BFS求出来

最后就枚举开头满足条件的质连通块然后把属于细胞的非质连通块打上标记，最后输出即可

代码很丑,贴链接吧