进行两次dfs,第一次将所有陆地归到各自的并查集中,并采用路径压缩将并查集中的所有点归到一个点上。
之后,再次进行dfs,扫描所有的海洋,统计与该海洋相邻的并查集的点的个数及该海洋点的个数,更新答案即可。
米小游和小美到达了一个被红色和海洋包裹着的星球,星球上有一些陆地,小美准备点燃其中一大片海。
具体来说,就是在一张二维地图上,分成了n×m个格子,每个格子的类型要么是大海,要么是陆地,若相邻(通过格子的边相邻)两个格子的类型相同,则视为同一个连通块,大海被点燃后会变成陆地,点燃一片大海就是把一个 大海连通块变成一个陆地连通块。
米小游想知道在小美最多点燃一片大海后,最大陆地连通块大小的最大值是多少。
第一行输入两个整数n,m(1≤n,m≤1000),表示地图大小。
接下来n行,每行输入一个长度为m的字符串s表示地图,其中'_'表示这个格子是大海,‘#’表示这个格子是陆地。
输出一个整数表示答案
输入
5 5
##..#
#..#.
###..
.#.#.
#.#..
输出
17
说明
点燃右下角的那一片大海,可以发现,点燃其他大海后的效果没有更优。