小塔和小美到达了一个被红色和海洋包裹着的星球,星球上有一些陆地,小美准备点燃其中一大片海。
具体来说,就是在一张二维地图上,分成了n×m个格子,每个格子的类型要么是大海,要么是陆地,若相邻(通过格子的边相邻)两个格子的类型相同,则视为同一个连通块,大海被点燃后会变成陆地,点燃一片大海就是把一个 大海连通块变成一个陆地连通块。
进行两次dfs,第一次将所有陆地归到各自的并查集中,并采用路径压缩将并查集中的所有点归到一个点上。
之后,再次进行dfs,扫描所有的海洋,统计与该海洋相邻的并查集的点的个数及该海洋点的个数,更新答案即可。