进行两次dfs,第一次将所有陆地归到各自的并查集中,并采用路径压缩将并查集中的所有点归到一个点上。
之后,再次进行dfs,扫描所有的水域,统计与该水域相邻的并查集的点的个数及该水域点的个数,更新答案即可。
你拥有一片 n 行 m 列的矩形区域,每个格子要么是陆地(用 '#' 表示),要么是水域(用 '.' 表示)。如果两个同类型的格子共用一条边(上下左右相邻),则它们属于同一个连通块。
你拥有一次特殊能力:选择恰好一片水域连通块,将其全部格子变为陆地。此后,这些新生成的陆地会与相邻的陆地连通块合并,形成更大的陆地连通块。
你的目标是使变化后的区域内,最大陆地连通块所包含的格子数尽可能大。请你求出这个最大值。
数据范围:行数 n 和列数 m 满足 1≤n,m≤1000。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册