wcwswswws的日记

wcwswswws

sgu320

sgu终于300了……

sgu320
题意：在n*m的土地上，一块连通的（上下左右）、且所占格数大于K的区域称为大区域。现在定义危险的格子：它们或者属于大区域，或者往上下左右任意方向走都必须经过同一块大区域。求危险格子数。

bfs，假设每个格子四条边上都是管道，一个大区域构成边界的管道使其中一些管道被封闭，那么从土地边界上任意一点flood-fill一遍就可以得出所有大区域的边界。所有属于大区域的格子或四边管道有一边没有水的格子之和就是答案。

posted on 2012-02-23 18:03 世界厕所所长 阅读(242) 评论(0)  编辑 收藏 引用 所属分类: ACM/ICPC


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理